[数学记录]AT3981 [ARC093D] Dark Horse

**题意** : 有 $2^n$ 个人，按照满二叉树的形态进行淘汰赛，一开始的排列顺序为所有 $(2^n)!$ 个排列之一。 你是第 $1$ 个人，已知每一对人之间的实力关系，具体地说： - 给出 $m$ 个人 $A_1 \sim A_m$。 - 这 $m$ 个人都打得过你。 - 你打得过除了这 $m$ 个人之外的所有其他人。 - 对于剩下的情况（你不参与的情况），编号小的人胜利。 问你在所有的 $(2^n)!$ 种情况中，有多少种情况可以取得最终胜利。答案对 $10^9 + 7$ 取模。 $n,m\leq 16$ ，时限$\texttt{2s}$。 ------------ 将比 $1$ 强的 $m$ 个人称为大佬。 首先将 $1$ 放在第一个位置，最后将答案乘以 $2^n$。 每个人都只会参与恰好 $n$ 场对局，而你只需要保证这 $n$ 场中没有遇到大佬。 各个对局分别对应大小为 $1,2,4,\dots 2^{n-1}$ 的子树。 考虑容斥。钦定对局集合 $S$，则要在对应子树中安排选手，使得被钦定的子树的最小值是大佬。 记方案数为 $g(S)$ ，则答案为 $2^n\sum\limits_{S}(-1)^{|S|}g(S)$。 考虑状压 $\rm DP$ ，按照编号从大到小的顺序考虑大佬（因为编号越大限制越强）。 设 $f[i,s]$ 为考虑了前 $i$ 个大佬，且子树集合 $s$ 被覆盖的贡献和。 在安排第 $i$ 个大佬时，可以不加入，也可以处理某个子树。 记 $siz(s)=\sum\limits_{j\in s}2^j$ ，即已经被安排好的子树大小和。 转移 : $f[i,s]=f[i-1,s]-\sum\limits_{j\in s}f[i-1,s-\{j\}]\big(2^n-A_i-siz(s-\{j\})\big)^{\underline {2^j-1}}2^j$ 其中 $\big(2^n-A_i-siz(s-\{j\})\big)^{\underline {2^j-1}}$ 是选出未被占用的比 $A_i$ 大的 $2^j-1$ 个垫背者，最后将 $A_i$ 加入有 $2^j$ 种方法。 其中下降幂可以预处理阶乘后快速计算。 边界 : $f[0,\varnothing]=1$ 最终需要考虑剩余数的排列，有 $g(s)=f[n,s]\big(2^n-1-siz(s)\big)!$ 复杂度 $O(nm2^n)$。（所以其实 $m$ 大一点也没关系的?） ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxS 66000 using namespace std; const int mod=1000000007; ll powM(ll a,int t=mod-2){ ll ret=1; while(t){ if (t&1)ret=ret*a%mod; a=a*a%mod;t>>=1; }return ret; } ll fac[MaxS],ifac[MaxS]; ll dpow(int k,int n) {return k<n ? 0 : fac[k]*ifac[k-n]%mod;} void Init(int n) { fac[0]=1; for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod; ifac[n]=powM(fac[n]); for (int i=n;i;i--) ifac[i-1]=ifac[i]*i%mod; } ll f[18][MaxS]; int cnt(int s){ int ret=0; while(s){s^=s&-s;ret++;} return ret; } int n,m,a[18]; int main() { scanf("%d%d",&n,&m); int tot=1<<n;Init(tot); for (int i=1;i<=m;i++)scanf("%d",&a[i]); reverse(a+1,a+m+1); f[0][0]=1; for (int i=1;i<=m;i++) for (int s=0;s<tot;s++){ f[i][s]=f[i-1][s]; for (int j=0;j<n;j++) if (s&(1<<j)) f[i][s]=(f[i][s]+f[i-1][s^(1<<j)]*dpow(tot-a[i]-(s^(1<<j)),(1<<j)-1)%mod*(1<<j))%mod; } ll ans=0; for (int s=0;s<tot;s++){ ll buf=f[m][s]*fac[tot-1-s]%mod; if (cnt(s)&1)ans-=buf;else ans+=buf; }ans=(ans%mod+mod)%mod; printf("%lld",(ans<<n)%mod); return 0; } ```