[DP][分治] 51Nod 1934 受限制的排列

Solution S o l u t i o n

一个显然的想法就是去找最小的那个数。

最小的数的 l l 和 rr 就应该是 1 1 和 nn 。

因为这是一个排列，我们把问题从最小值处 pos p o s 分开，得到两个一样的问题 (1,pos−1) ( 1 , p o s − 1 ) 和 (pos+1,n) ( p o s + 1 , n ) 。设区间长度为 len l e n ，分出的两个区间长度为 lenl,lenr l e n l , l e n r ，贡献就是这两个问题的答案的积乘上 (len−1lenl) ( l e n − 1 l e n l ) 。

找最小值可以暴力用 map map 存下来就好啦~

O(nlogn) O ( n log ⁡ n ) 。

题解的说法是这是个笛卡尔树。。吧

#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef pair<int, int> pairs;
const int N = ;
const int MOD = ;

inline char get(void) {
    static char buf[], *S = buf, *T = buf;
    if (S == T) {
        T = (S = buf) + fread(buf, , , stdin);
        if (S == T) return EOF;
    }
    return *S++;
}
template<typename T>
inline int read(T &x) {
    static char c; x = ; int sgn = ;
    for (c = get(); c < '0' || c > '9'; c = get()) {
        if (c == '-') sgn = ;
        if (c == EOF) return ;
    }
    for (; c >= '0' && c <= '9'; c = get()) x = x *  + c - '0';
    if (sgn) x = -x; return ;
}

int n, test;
int l[N], r[N];
int fac[N], ifac[N];
map<int, int> mp[N];

inline void pre(int n) {
    ifac[] = ;
    for (int i = ; i <= n; i++)
        ifac[i] = (ll)(MOD - MOD / i) * ifac[MOD % i] % MOD;
    fac[] = ifac[] = ;
    for (int i = ; i <= n; i++) {
        fac[i] = (ll)fac[i - ] * i % MOD;
        ifac[i] = (ll)ifac[i - ] * ifac[i] % MOD;
    }
}
inline int C(int n, int m) {
    return (ll)fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
inline int solve(int dl, int dr) {
    if (dl > dr) return ;
    int pos = mp[dl][dr];
    if (dl == dr && pos == dl) return ;
    if (pos < dl || pos > dr) return ;
    int res = (ll)C(dr - dl, pos - dl) * solve(dl, pos - ) % MOD * solve(pos + , dr) % MOD;
    return res;
}

int main(void) {
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    pre();
    while (read(n)) {
        ++test;
        for (int i = ; i <= n; i++) read(l[i]);
        for (int i = ; i <= n; i++) read(r[i]);
        int f = ;
        for (int i = ; i <= n; i++) {
            if (mp[l[i]].count(r[i])) f = ;
            mp[l[i]][r[i]] = i;
        }
        if (f) printf("Case #%d: %d\n", test, solve(, n));
        else printf("Case #%d: 0\n", test);
        for (int i = ; i <= n; i++) mp[i].clear();
    }
    return ;
}