ARC093F Dark Horse

Description

$\text{Link}$

Solution

西哥挖坟挖出来一道神仙题。

考虑问题本质：给定集合 $\mathcal{A}$ ，和 $n$ 个集合 $\mathcal{Q_1}=\{2\},\mathcal{Q_2}=\{3,4\},\cdots$ ，要求构造排列 $\mathcal{P}$ ，满足 $\forall i\in [1,n]$ ，将 $\mathcal{Q}_i$ 集合中的数视作下标时，对应的 $\mathcal{P}_j$ 的最小值均不在 $\mathcal{A}$ 中。

考虑容斥，每次钦定一个 $\mathcal{S}=\{\mathcal{Q}_1,\mathcal{Q}_2,\cdots\}$ 的子集 $\mathcal{T}$ 不满足要求，并求出方案数。

钦定的时候可以这样考虑：假设将 $\mathcal{A}$ 降序排序后，已经用到了第 $i$ 个，那么我们在填当前集合 $\mathcal{Q}_k$ 时，我们把 $\mathcal{A}_i$ 和 $2^k-1$ 个比 $\mathcal{Q}_k$ 大的元素和 $\mathcal{A}_i$ 一起放进 $\mathcal{Q}_k$ 中。

据此可以设计动态规划。设 $f_{i,s}$ 表示已经在将 $\mathcal{A}$ 降序排序后，用到了第 $i$ 个，集合 $s$ 内的 $\mathcal{Q}$ 已经填完了的方案数。可以发现，当用二进制来表示 $s$ 时， $s$ 既是已经填了的 $\mathcal{Q}$ 的状态，也表示已经用了 $s$ 个大于等于 $\mathcal{A}_i$ 的数。 考虑转移。既可以用 $\mathcal{A}_{i+1}$ 新填一个集合，也可以什么也不做，留着第 $i$ 个数以后再填。故有：

$f_{i-1,s}\leftarrow f_{i,s}\\ f_{i-1,s|j}\leftarrow f_{i,s}\times \binom{2^n-s-a_{i-1}}{2^j-1}\times (2^j)!$

考虑最后钦定仅填了集合 $s$ 内的 $\mathcal{Q}$ 的方案数就是 $f_{1,s}$ ，剩下的数我们任意填即可。所以再乘上一个阶乘。

复杂度 $\mathcal{O}(nm2^n)$ 。

感觉这个题很重要的一点是想清楚如何去「钦定」，将 $\mathcal{A}_i$ 降序排序再一个一个插入集合内是很聪明的办法。

Code

const int N = 1e6 + 6, M = 20, mod = 1e9 + 7;
using namespace std;
int n, m;
int a[M], sz[N], fac[N], inv[N], invf[N];
int f[M][N];

int binom(int n, int m){
    if(n < 0 || m < 0 || n - m < 0) return 0;
    return 1ll * fac[n] * invf[m] % mod * invf[n - m] % mod;
}
void prework(int n){
    fac[0] = fac[1] = inv[0] = inv[1] = invf[0] = invf[1] = 1;
    for(int i = 2; i <= n; ++i)
        fac[i] = 1ll * fac[i - 1] * i % mod,
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod,
        invf[i] = 1ll * inv[i] * invf[i - 1] % mod;
}
int main(){
    
    fin >> n >> m;

    prework(1e6);

    for(int i = 1; i <= m; ++i)
        fin >> a[i];
    f[m + 1][0] = 1;
    for(int i = m; i >= 1; --i)
    for(int j = 0; j < (1 << n); ++j) if(f[i + 1][j]) {
        (f[i][j] += f[i + 1][j]) %= mod;
        for(int k = 0; k < n; ++k) if(!((j >> k) & 1))
            (f[i][j | (1 << k)] += 1ll * f[i + 1][j] * binom((1 << n) - a[i] - j, (1 << k) - 1) % mod * fac[1 << k] % mod) %= mod;
    }

    int ans = 0;
    for(int i = 0; i < (1 << n); ++i){
        sz[i] = sz[i >> 1] + (i & 1);
        int v = 1ll * f[1][i] * fac[(1 << n) - 1 - i] % mod;
        if(sz[i] & 1) ans = (ans + mod - v) % mod;
        else ans = (ans + v) % mod;
    }
    cout << 1ll * ans * (1 << n) % mod << endl;
    return 0;
}