[ARC093D] Dark Horse

一、题目

点此看题

二、解法

以前我是做过类似的题的，但是现在为什么这都做不来了呢？

我们先把 \(1\) 固定在 \(1\) 号位计算，最后再把答案乘上 \(2^n\) 即可。对 \(1\) 打到根的这条链进行计数，考虑容斥原理，如果 \(a_1,a_2...a_m\) 中的某个人出现在了这条链上，就增加 \(-1\) 的容斥系数，剩下的人可以任意排列。

考虑 \(dp\) 计算容斥系数，我们按照编号从大到小的顺序来 \(dp\)，设 \(dp[i][s]\) 为考虑 \(m\) 个人的前 \(i\) 个（排序后），占据链上位置集合是 \(s\) 的容斥系数。那么转移考虑第 \(i\) 个人不在链上，或者占据链上的某个位置：

\[dp[i][s]\leftarrow dp[i-1][s]\\dp[i][s|2^j]\leftarrow dp[i-1][s]\cdot {2^n-s-a_i\choose 2^{j}-1}\cdot 2^j! \]

时间复杂度 \(O(nm2^n)\)

#include 
#include 
using namespace std;
const int M = (1<<16)+5;
const int MOD = 1e9+7;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,ans,a[20],fac[M],inv[M],dp[20][M];
void add(int &x,int y) {x=(x+y)%MOD;}
void init(int n)
{
	fac[0]=inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
	for(int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[i]%MOD;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
}
int C(int n,int m)
{
	if(n<0 || nj;});
	dp[0][0]=1;
	for(int i=1;i<=m;i++) for(int s=0;s<(1<>j&1))
		{
			add(dp[i][s|(1<


						
							

						
							
							
			数学-容斥原理dp-状压dp数学-计数原理

[ARC093D] Dark Horse

一、题目

二、解法

相关

标签