OI - Everything on It(AtCoder)

看到计数题就直接来

---

# 题面

> Linked AtCoder ARC096-E

点击展开/折叠题面

有 $n$ 个元素，求有多少种 $\{1,2,\dots,n\}$ 的子集的集合使得每个元素在这些子集中出现了至少两次。

形式化地，求 $S=\{s_1,s_2,\dots,s_k\}$ 的数量，满足：

$$ \forall i,\sum_{j=1}^k[i\in s_k]\ge 2 $$

$1\le n\le3000$，答案对输入的质数 $M$ 取模。

---

# 解析

其实并没有直接来……

正着考虑“每个元素都出现了不小于两次”非常复杂，那就倒过来容斥。

设 $f_i$ 表示恰好有 $i$ 个元素出现了小于两次，则有容斥套路——设 $g_i$ 表示钦定有 $i$ 个元素出现了小于两次。

$$g_i=\sum_{j=i}^n\binom{j}{i}f_j\Leftrightarrow f_i=\sum_{j=i}^n(-1)^{i-j}\binom jig_j$$

然后就是怎么算 $g$ 的问题了，就可以直接来推式子。

• 从 $n$ 里选出钦定的 $i$ 个数 $\binom ni$；
• 不包含钦定的 $i$ 个数的子集的方案数：不包含钦定的数的子集共 $2^{n-i}$ 个，每个子集在集合 $S$ 中有没有都无所谓，总方案数为 $2^{2^{n-i}}$；

• 包含钦定的数的子集，注意到这些子集可以包含没有被钦定的数，所以讨论起来比较复杂，需要知道这些子集具体有多少个。

  因为每个钦定的数最多出现一次，所以这些子集的数量不超过 $i$ 个，直接枚举数量为 $j$ 个：

  • 注意现在枚举的这 $j$ 个子集都必须包含钦定的数；

  • 也就是把 $i$ 个不同的数，要么分到 $j$ 个没有区别的集合里（出现一次），要么丢掉不要（不出现）；

    丢掉不要的数并不好处理，再用一个集合放这些丢掉的数，这个集合不同于其他 $j$ 个集合，并且可以为空；

    怎么体现丢掉的数的集合与其他集合不同？这个时候我们已经感觉到与第二类斯特林数有一些联系了；

  • 整理一下问题：“把 $i$ 个有标号球放进 $j$ 个普通盒子与一个特殊盒子，普通盒子不能空，特殊盒子可以为空”；

    运用斯特林数递推式的推导思想，再添加一个有标号球，在一开始就把它放进所有 $j+1$ 个盒子中的一个——于是放入的这个盒子变特殊了，这个盒子就是“丢掉的数的集合”；

  • 所以方案数就是斯特林数 $S(i+1,j+1)$；

  • 还没完，这 $j$ 个子集里还可以包含非钦定的数，任意一个子集都可以包含 $n-i$ 个非钦定数的任意一部分，则 $j$ 个子集的方案数就还需要乘上 $(2^{n-i})^j$；

  综上，包含钦定的数的子集的方案数为

  $$\sum_{j=0}^iS(i+1,j+1)2^{(n-i)j}$$

预处理 $2$ 的幂，$n^2$ 个斯特林数和 $n^2$ 个组合数，就可以 $O(n^2)$ 求出 $g_0\sim g_n$。

最后答案就是

$$f_0=\sum_{i=0}^n(-1)^ig_i$$

有个小坑点在于计算 $2^{2^{n-i}}$ 时，指数的 $2^{n-i}$ 需要对 $MOD-1$ 取模（费马小定理）。

---

# 源代码

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=3005;
int MOD;
#define ci const int &

inline int Add(ci a,ci b,ci mod=MOD){return a+b>=mod? a+b-mod:a+b;}
inline int Sub(ci a,ci b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(ci a,ci b){return int(1ll*a*b%MOD);}
inline int Pow(ci a,ci b){return b? Mul(Pow(Mul(a,a),b>>1),(b&1)? a:1):1;}

int n;
int comb[N][N],S[N][N],F[N][N],pow2[N*N],pow2_[N*N],g[N];

void Init(){
	for(int i=0;i<N*N;i++)
		if(i){
			pow2[i]=Add(pow2[i-1],pow2[i-1]);
			pow2_[i]=Add(pow2_[i-1],pow2_[i-1],MOD-1);
		}
		else pow2[i]=pow2_[i]=1;
	S[0][0]=1;
	for(int i=0;i<N;i++){
		comb[i][0]=1;
		for(int j=1;j<=i;j++){
			comb[i][j]=Add(comb[i-1][j-1],comb[i-1][j]);
			S[i][j]=Add(S[i-1][j-1],Mul(j,S[i-1][j]));
		}
	}
}
int main(){
	scanf("%d%d",&n,&MOD);
	Init();
	for(int i=0;i<=n;i++){
		g[i]=Mul(comb[n][i],Pow(2,pow2_[n-i]));
		int sum=0;
		for(int j=0;j<=i;j++)
			sum=Add(sum,Mul(S[i+1][j+1],pow2[(n-i)*j]));
		g[i]=Mul(g[i],sum);
	}
	int ans=0;
	for(int i=0;i<=n;i++)
		if(i&1) ans=Sub(ans,g[i]);
		else ans=Add(ans,g[i]);
	printf("%d\n",ans);
	return 0;
}

---

THE END

Thanks for reading!

$$\begin{split} “\ &有人说\ 何必大惊小怪只是孩子谁没有过\ 年少轻狂\\ &有人说\ 那么多人就你被欺负\ 应该自认悲伤做伪装\\ &有人说\ 站在受害人角度不够理性\ 那么无知被原谅\\ &我想把少年犯的刀送进他们胸膛\ 可不能\ 这样\ ”\\ ——&\text{《年少无罪》By 祖娅纳惜} \end{split}$$

> Linked 年少无罪-网易云