数学、容斥原理、动态规划

题目链接

非常感谢 gza 老师讲解。

本文中使用 $m$ 表示势力数量。

考虑容斥，算出能发起反叛的排列的数量，如果能由前 $i$ 个势力一起发动反叛，就认为 $i$ 是坏的。

钦定集合 $S$ 中的位置为坏的（不管其余位置的好坏），如果有 $x$ 个排列的坏位置包含了 $S$ 中的所有坏位置，那么 $S$ 对答案的贡献为 $(-1)^{ |S|+1 } \times x$。

很显然这个容斥直接做至少是 $O(2^{m})$ 的，那样就炸了。

设计 $dp_i$ 为集合 $S$ 中最大的数为 $i$ 时，所有可能的 $S$ 对应的 $(-1)^{ |S|+1 } \times x$ 之和。

转移的时候肯定不能把每个 $S$ 枚举出来然后乘上容斥系数 $(-1)^{ |S|+1 }$，不然复杂度也会炸，好在状态定义里是包含容斥系数的，转移的时候只需要乘一个 $-1$，记 $s_i = \sum\limits_{j=1}^{i} k_j$，令 $dp_0 = 0$，写出状态转移方程。

$$dp_{i} = \sum_{j=1}^{i-1} (-1) dp_j \frac{(s_i - s_j)! (n - s_i)!}{(n - s_j)!} + s_i ! (n - s_i)!$$

答案即为 $n! - \sum\limits_{i=1}^{n} dp_i$ 的值。

预处理阶乘和阶乘逆元，总体时间复杂度 $O(n + m^2)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=1'000'000'007;
int n,m,ans,s[5'005],dp[5'005],fac[1'000'005],inv[1'000'005];
int mul(int x,int y){
    int ret=1;
    while(y){
        if(y&1) ret=1ll*ret*x%mod;
        x=1ll*x*x%mod,y>>=1;
    }
    return ret;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        static int x;
        scanf("%d",&x);
        s[i]=s[i-1]+x;
    }
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=mul(fac[n],mod-2);
    for(int i=n;i>=1;i--) inv[i-1]=1ll*inv[i]*i%mod;
    for(int i=1;i<=m;i++){
        dp[i]=1ll*fac[s[i]]*fac[n-s[i]]%mod;
        for(int j=1;j<=i-1;j++)
            dp[i]=(dp[i]+(-1ll)*dp[j]*fac[s[i]-s[j]]%mod*fac[n-s[i]]%mod*inv[n-s[j]])%mod;
        ans=(ans+dp[i])%mod;
    }
    ans=((fac[n]-ans)%mod+mod)%mod;
    printf("%d\n",ans);
    return 0;
}