Atcoder Regular Contest 093 D - Dark Horse（组合数学+状压 dp）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

Atcoder 题面传送门 & 洛谷题面传送门

常规题，简单写写罢（（（

首先 \(1\) 的位置是什么不重要，我们不妨钦定 \(1\) 号选手最初就处在 \(1\) 号位置，最后答案乘个 \(2^n\) 即可。

显然与 \(1\) 进行比赛的选手一定是区间 \([2,2],[3,4],[5,8],\cdots,[2^{k-1}+1,2^k],\cdots,[2^{n-1}+1,2^n]\) 中的最小值，而由于我们希望 \(1\) 号选手在比赛中取得胜利，故 \([2,2],[3,4],[5,8],\cdots,[2^{k-1}+1,2^k],\cdots,[2^{n-1}+1,2^n]\) 的最小值中不能出现打得过 \(1\) 的选手，于是问题转化为，有多少个 \(2\sim 2^n\) 的排列，使得任意 \(a_i\) 都不是 \([2,2],[3,4],[5,8],\cdots,[2^{k-1}+1,2^k],\cdots,[2^{n-1}+1,2^n]\)。

直接计算不是太容易，考虑容斥，记 \(F(i)\) 为钦定 \(i\) 个 \(a_j\) 是 \([2,2],[3,4],[5,8],\cdots,[2^{k-1}+1,2^k],\cdots,[2^{n-1}+1,2^n]\) 的最小值，剩余随便填的方案数，根据二项式反演，\(ans=\sum\limits_{i=0}^mF(i)(-1)^i\)。

那么怎么求 \(F(i)\) 呢？考虑状压 dp，\(dp_{i,j}\) 表示考虑了 \(a_1\sim a_i\)，\(j\) 是一个二进制数，\(j\) 的 \(2^k\) 位为 \(1\) 当且仅当长度为 \(2^k\) 的区间的最小值已经被钦定为 \(a_1\sim a_i\) 中的某个值。考虑转移，显然可以枚举 \(a_{i+1}\) 是否被选择来转移，但是由于你不知道 \((a_i,a_{i+1})\) 中有多少个数已经被填了，故无法计算方案数，因此这个状态设计是不可行的。考虑换个角度，我们反着 \(dp\)，\(dp_{i,j}\) 表示考虑了 \(a_{m-i+1}\sim a_m\)，这样转移时候，所有被填入 \(j\) 中的区间的数都是 \(\ge a_{m-i+1}\) 的数，转移就容易了许多。枚举 \(a_{m-i}\) 填入了长度为多少的区间，假设为长度为 \(2^k\) 的区间，那么相当于在 \((a_{m-i},2^n]\) 中未填入钦定的区间中的 \(2^n-a_{m-i}-j\) 个数中选择 \(2^k-1\) 个数并排列好，方案数为 \(\dbinom{2^n-a_{m-i}-j}{2^k-1}\times (2^k)!\)，预处理组合数转移即可，时间复杂度 \(n^22^n\)。

const int MAXN=16;
const int MAXP=1<<16;
const int MOD=1e9+7;
int n,m,lim,a[MAXN+3],fac[MAXP+5],ifac[MAXP+5];
int dp[MAXN+3][MAXP+5];
void initfac(int n){
fac[0]=ifac[0]=ifac[1]=1;
for(int i=2;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;
}
int binom(int x,int y){
if(x<y||x<0||y<0) return 0;
return 1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;
}
int main(){
scanf("%d%d",&n,&m);lim=1<<n;initfac(lim);
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
reverse(a+1,a+m+1);dp[0][0]=1;
for(int i=0;i<m;i++) for(int j=0;j<lim;j++){
for(int k=0;k<n;k++) if(~j>>k&1){
dp[i+1][j|(1<<k)]=(dp[i+1][j|(1<<k)]+1ll*dp[i][j]*binom(lim-a[i+1]-j,(1<<k)-1)%MOD*fac[1<<k])%MOD;
} dp[i+1][j]=(dp[i+1][j]+dp[i][j])%MOD;
}
int ans=0;
for(int i=0;i<lim;i++){
int cnt=__builtin_popcount(i),ways=1ll*dp[m][i]*fac[lim-1-i]%MOD;
if(cnt&1) ans=(ans-ways+MOD)%MOD;else ans=(ans+ways)%MOD;
} printf("%d\n",1ll*ans*lim%MOD);
return 0;
}