Solution P10813 | He was My Friend

· · 题解

一个经典 trick：考虑值域为 \{0,1\} 的时候怎么做。

发现非常简单粗暴：可以直接枚举 2^n 种可能性，然后模拟 m 次操作，再检验操作完毕后是否有序。因此进行一个 \mathcal{O}(m2^n) 的预处理。

在值域变大的情况下，我们可以将其拆成多个值域为 \{0,1\} 的情况。即，对于任意 2 \le i \le V，将 a 中 <i 的数视作 0，\ge i 的数视作 1，对于构造出的 \{0, 1\} 序列应依然满足题意要求，而判断其是否满足是可以利用上面所预处理的内容。

设 f_{i,j} 表示值域为 i，当前二进制数为 j 的情况。转移就是每次转移到 j 的一个合法子集（或超集，即倒着做，依然能得到正确结果）。

利用高维前缀和可以做到 \mathcal{O}(nV2^n)。

令 g(x) 为 V=x 的答案，h(x) 为序列中恰好有 x 种数的答案（相当于 V=x，且 1 \sim x 中所有数均出现，不难发现 x \le n 才有值），发现 g(x) = \sum \limits_{k} \binom{x}{k}h(k)，即 g(x) 是关于 x 的 n 次多项式。

可以算 g(x) 拉插一下（比较常见的套路），也可以直接算 h(x) 然后算组合数。

时间复杂度 \mathcal{O}((n^2+m)2^n)。

ll n,V,m,p[505],q[505],f[20][1<<18],w[20];
bool vis[1<<18], t[30];
void addmod(ll &x){ if(x >= mod) x -= mod; }
void solve(){
    n=read(), V=read(), m=read();
    for(ll i=1;i<=m;i++){
        p[i]=read()-1, q[i]=read()-1;
    }
    for(ll i=0;i<(1<<n);i++){
        for(ll j=0;j<n;j++) t[j]=((i>>j)&1);
        for(ll j=1;j<=m;j++){
            if(t[p[j]] > t[q[j]]) swap(t[p[j]], t[q[j]]);
        }
        vis[i] = 1;
        for(ll j=1;j<n;j++) if(t[j-1] > t[j]) vis[i]=0;
    }
    f[0][0] = 1;
    for(ll i=1;i<=n;i++){
        for(ll j=0; j<(1<<n); j++) f[i][j] = f[i-1][j];
        for(ll j=0; j<n; j++)
            for(ll k=0; k<(1<<n); k++){
                if((k>>j)&1) continue;
                addmod(f[i][k^(1<<j)] += f[i][k]);
            }
        for(ll k=0; k<(1<<n); k++)
            if(!vis[k]) f[i][k] = 0;
    }
    ll ans = 0;
    for(ll i=0;i<=n;i++){
        for(ll j=0; j<(1<<n); j++) addmod(w[i+1] += f[i][j]);
    }
    for(ll i=1;i<=n+1;i++){
        ll xs = 1;
        for(ll j=1; j<=n+1; j++) if(j!=i) xs = xs * qpow(i-j+mod, mod-2) % mod;
        for(ll j=1; j<=n+1; j++) if(j!=i) xs = xs * (V-j+mod) % mod;
        ans = (ans + xs * w[i]) % mod; 
    }
    printf("%lld\n", ans);
}