专栏文章

题解：[ARC093F] Dark Horse

LLin_Yunxi
AT_arc093_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir2q6v4
此快照首次捕获于
2025/12/04 14:47
3 个月前
此快照最后确认于
2025/12/04 14:47
3 个月前
查看原文

AT_arc093_d

题目描述

给定 nn，mm ，问在有 mm 个编号为 aia_i 的选手不可战胜的情况下，在一个 2n2^n 的满二叉树上进行淘汰制比赛，获胜的情况数
具体解释，你是 11 号选手，你无法战胜的选手有且仅有那 mm 个，对于剩下的情况（你不参与的情况），编号小的人胜利，选手编号 ≤2n\le2^n。

题目分析

由于不管 11 在哪个位置，一轮轮下来，基本上过程都是相似的，所以假设 11 在第 11 个位置。
令集合 aa 表示无法战胜的选手，集合 pp 表示所有选手
它所遇见对手的情况无非是p1,min⁡(p2,p3),min⁡(p4,p5,p6,p7),...p_1,\min{(p_2,p_3)},\min{(p_4,p_5,p_6,p_7)} ,...
把这些人分别用 b0,b1,b2,...b_0,b_1,b_2,... 表示，因此我们要求的就是：使得任意 x∈bx\in b 且 x∉ax\notin a ，它们的情况数目
发现 ∣b∣=n\vert b \vert =n ，较小 ，所以想到状压 ， 用 SS 表示 ， SS 中的 11 表示该位置 bi∈ab_i\in a ，定义 dp[i][S]dp[i][S] 表示集合 SS 中的 bb 值均出现在 aa 中前 ii 个数的方案数。
？？？？？？ 你问我不是要的是 b,ab,a 中元素不相同吗？？
如果真的要这样就太复杂了
那我们反过来 ，考虑容斥 ，定义函数 count(x)count(x) 表示 xx 在二进制下 11 数量的奇偶性 ， 奇返回 −1-1 ， 偶返回 11 ， 令 SS 上界为 NN ， 可以证明最终结果 ans=∑S=0Ncount(S)×dp[m][S]ans=\sum_{S=0}^{N} count(S)\times dp[m][S]
现在来考虑 dpdp 的转移 ：
  • 不选第 ii 个数 ， dp[i][S]→dp[i+1][S]dp[i][S]\rightarrow dp[i+1][S]
  • 选了第 ii 个数 ， 此时我们要去找 SS 中有 00 的位置 jj ， 把它填成 aia_i 。jj 对应 bjb_j ，不难分析 ， bjb_j 应该是由 2j2^j 个数字取 minmin 得到 ， 一个位置填 aia_i ， 剩下 2j−12^j-1 个位置都应该取比 aia_i 大且没有被选的数 （ 规则是这样说的 ） ，故有以下转移 ：
CPP
for(int j=0;j<n;j++)
{
    if(!((S>>j)&1))
    {
    	les=(1<<n)-a[i]-S;
    	dp[i+1][S|(1<<j)]+=dp[i][j]*C(les,(1<<j)-1));	
	}	
}
其中 C(n,m)C(n,m) 表示从 nn 个数中选 mm 个数的方案数 ，不用多说
lesles 代表剩下可以选的数 ，(1<<n)(1<<n) 表示总数 ，上面分析 bjb_j 性质可以推出 ，SS 既可以表示状态也可以表示已经选了多少个数
为了方便计数 ， 将 aa 从大到小排序
最后，由于转移后没有考虑到 SS 中剩下 00 中的选择情况 ， 还要乘上 (2n−1−S)!(2^n-1-S)! （也是由此推出容斥原理）
时间复杂度 O(2nnm)O(2^nnm)

codecode

CPP
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) x&(-x)
using namespace std;
const int N=20,K=(1<<16)+7,p=1e9+7;
int n,m;
int a[N];
ll dp[N][K],ans;
ll fac[K],inv[K];
ll qpow(ll x,int n,ll res=1)
{
	while(n)
	{
		if(n&1)	res=res*x%p;
		x=x*x%p;
		n>>=1;
	}
	return res;
}
bool cmp(int a,int b)
{
	return a>b;
}
void init(int n)
{
	fac[0]=inv[0]=1;
	for(int i=1;i<=n;i++)	fac[i]=fac[i-1]*i%p;
	inv[n]=qpow(fac[n],p-2);
	for(int i=n-1;i>=1;i--)	inv[i]=inv[i+1]*(i+1)%p;
}
ll C(int n,int m)
{
	if(n<m)	return 0;
	return fac[n]*inv[m]%p*inv[n-m]%p;
}
int get_cnt(int x,int ans=0)
{
	while(x)
	{
		ans++;
		x-=lowbit(x);
	}
	return ans;
}
int main()
{
    scanf("%d%d",&n,&m);init(1<<n);
    for(int i=1;i<=m;i++)	scanf("%d",&a[i]);
    sort(a+1,a+m+1,cmp);
    dp[0][0]=1;
    for(int i=0;i<m;i++)
    {
    	for(int j=0;j<(1<<n);j++)
    	{
    		int t=(1<<n)-a[i+1]-j;
    		dp[i+1][j]=(dp[i+1][j]+dp[i][j])%p;
    		for(int k=0;k<n;k++)
    		{
    			if(!((j>>k)&1))
    			{
    				dp[i+1][j|(1<<k)]=(dp[i+1][j|(1<<k)]+dp[i][j]*C(t,(1<<k)-1)%p*fac[1<<k]%p)%p;
				}
			}
		}
	}
	int S=(1<<n)-1;
	for(int i=0;i<=S;i++)
	{
		int cnt=get_cnt(i);
		if(cnt&1)	ans=(ans-dp[m][i]*fac[S-i]%p+p)%p;
		else	ans=(ans+dp[m][i]*fac[S-i]%p)%p;
	}
	ans=ans*(S+1)%p;
	printf("%d",ans);
	return 0;
}
是不是发现最后 ansans 乘上了一个 2n2^n ，因为 11 可以出现在 2n2^n 个位置

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...