NOD2308B. 酒杯（glass）

题意

有一棵 \(n\) 层的满二叉树，有 \(m\) 次操作，每次操作从 \(2^n-1\) 个节点中随机选择一个节点染黑（可以重复染色），问使得每一层都至少有一个节点被染黑的方案数。\(n,m\le 2000\)，答案对 \(10^9 + 7\) 取模。

solution

%%% 蔡队

显然问题可以简化成有 \(n\) 个点，第 \(i\) 个点有 \(2^{i-1}\) 种方式可以被染黑，问所有点都被染黑的方案数。

暴力就是枚举每次操作染了哪个点。

直接统计染上所有点的方案数是不好统计的。但是算至多可以染某些点的方案数是好算的。

考虑容斥。用点集 \(S\) 表示不允许染 \(S\) 里面的点。

子集枚举。（题解叫做子集反演）

根据直觉变一下形（实际上可以看做是设 \(S\) 表示允许染色的点集），那么有更加优美的式子：

换个名字，写成：

直接做这个东西的复杂度是 \(O(2^n\log m)\) 的。测试点 \(6\sim 8\) 必须（？）这个做法。

发现 \(f(n,m)\) 的个数是 \(nm\) 的，考虑变成递推转移。

假设我们考虑完前 \(n-1\) 个点，然后再加上第 \(n\) 个点，假设我们的 \(i\) 是把序号小的放在低位，有：

表示子集枚举前 \(i\) 个点的选择状态，乘方案数的时候枚举是否选择第 \(n\) 个数。\(2i\) 的状态表示不选，\(2i+1\) 的状态表示选择。

根据二项式定理：\((x+y)^n = \sum_{i=0}^n \binom{n}{i} x^{n-i}y^i\)。

把 \((2i+1)^m\) 拆开，变成 \(\sum_{k=0}^m \binom{m}{k} (2i)^k\)。

有：

若 $i$ 是把序号大的放在低位，式子会变好看吗？

\[\begin{aligned} f(n,m) & =\sum_{i=0}^{2^{n-1}-1} (-1)^{n-count(i)} ( i^m - (i+2^n)^m )\\ & = \sum_{i=0}^{2^{n-1}-1} (-1)^{n-count(i)} (-\sum_{k=1}^m \binom{m}{k} i^{m-k} 2^{nk})\\ & = \sum_{i=0}^{2^{n-1}-1} (-1)^{n-count(i)-1} (\sum_{k=1}^m \binom{m}{k} i^{m-k} 2^{nk})\\ & =\sum_{k=1}^m \binom{m}{k} 2^{nk} \sum_{i=0}^{2^{n-1}-1} (-1)^{n-count(i)-1} i^{m-k}\\ & = \sum_{k=1}^m \binom{m}{k} 2^{nk} f(n-1,m-k) \end{aligned} \]

本质上是一样的，而且并不会更加优美。

至此你获得了转移复杂度为 \(O(m)\) 的递推式。状态是 \(O(nm)\)，总时间复杂度是 \(O(nm^2)\)。

边界条件是 \(f(1,0)=0,f(1,k=1\sim m)=1\)。

蔡队的分段打表方法（很有学习意义）

发现 \(f(n,m)\) 只和 \(f(n-1,k)\) 有关，因此对于第一维每隔 \(B\) 打一个长度为 \(m\) 的表。

然后发现空间不够。为什么 cplusoj 只能上传 50kb 的代码？解决方法是把表压成字符，使用表的时候进行解码操作。

题解提出倍增优化。

也许突破口是 \(f(n,m)\) 的具体意义感觉可以倍增？或许是因为 \(f(n,m)\) 只和 \(f(n-1)\) 有关，所以想要优化第一维的递推？类似于快速幂？

根据 \(f(2n,m)\) 的具体意义。考虑子集枚举前 \(n\) 个数的选择状态，乘方案数的时候枚举后 \(n\) 个数的选择状态。

好像……解决啦。Hooray!

但是 \(n\) 不一定是 \(2\) 的幂次怎么办呢？能否推广？

太优美了！可以推广！

更加优美的做法（来自 @gzyqwq 的建议）

其实不需要推广，因为我们已经有了 \(f(n) \gets f(n-1)\) 的公式，因此如果 \(n\) 是奇数就从 \(n-1\) 转移，否则从 \(\frac{n}{2}\) 转移。时间仍然是 \(\log\) 的。可以少推一个式子。

那么就做完了，对 \(n\) 这一维倍增，时间复杂度 \(O(m^2 \log n)\)。

code

代码很好实现也很好理解。本题难度主要在推式子。

#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
constexpr int mod=1e9+7;
constexpr int N=2e3+7;
int n,m;
ll ksm(ll a,ll b=mod-2) {
	ll s=1;
	while(b) {
		if(b&1) s=s*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return s;
}
ll add(ll a,ll b) { return a+b>=mod?a+b-mod:a+b; }
namespace sub1 {
	ll ans;
	void main() {
		rep(i,0,(1<<n)-1) ans=add(ans,add(mod,((n-__builtin_popcount(i))&1?-1ll:1ll)*ksm(i,m)));
		pf("%lld\n",ans);
	}
}
namespace sub2 {
	ll ans[N],tmp[N];
	ll f[30][N];
	ll mi2[N*N];
	ll binom[N][N];
	void main() {
		int lg=__lg(n);
		mi2[0]=1;
		rep(i,1,n*m) mi2[i]=add(mi2[i-1],mi2[i-1]);
		binom[0][0]=1;
		rep(i,1,m) {
			binom[i][0]=binom[i-1][0];
			rep(j,1,i) binom[i][j]=add(binom[i-1][j-1],binom[i-1][j]);
		}
		rep(i,1,m) f[0][i]=1;
		rep(i,1,lg) {
			rep(j,0,m) {
				rep(k,0,j) f[i][j]=add(f[i][j],binom[j][k]*mi2[k<<(i-1)]%mod*f[i-1][j-k]%mod*f[i-1][k]%mod);
			} 
		}
		int x=0;
		ans[0]=1;
		rep(i,0,lg) {
			if((n>>i)&1) {
				memcpy(tmp,ans,sizeof(tmp));
				rep(j,0,m) {
					ans[j]=0;
					rep(k,0,j) ans[j]=add(ans[j],binom[j][k]*mi2[x*k]%mod*tmp[j-k]%mod*f[i][k]%mod);
				}
				x+=1<<i;
			} 
		} 
		pf("%lld\n",ans[m]);
	}
}
int main() {
	#ifdef LOCAL
	freopen("my.out","w",stdout);
	#else
	freopen("glass.in","r",stdin);
	freopen("glass.out","w",stdout);
	#endif
	sf("%d%d",&n,&m);
	if(m==1145141919) sub1 :: main();
	else sub2 :: main();
}