首先我们把每道题 H 看做 $1$，E 看做 $0$ 的话，那么条件变成了选若干道题并排序，使得相邻两项满足前一项是后一项的子集。

把状态相同的题目放在一起考虑，假设有 $k$ 道题，那么选择至少一题的方案数就是：

可以直接预处理。那么现在我们需要按顺序进行 DP 转移，有以下几种方法：

直接暴力

定义 $dp_{S}$ 表示最后一项是 $S$ 的选法的方案数，那么每次的转移我们需要枚举 $S$ 的所有子集进行转移，按 $S$ 大小依次转移。直接转移的总复杂度为 $O(3^m)$。

分成前后两部分

这套路某年 CSP 初赛考过。

刚才的瓶颈在于枚举子集，那能不能改进一下。考虑 $s_{i,j}$ 表示所有 $dp_{x}$ 的和，其中 $x$ 需要满足前 $10$ 位是 $i$，后 $10$ 位是 $k$，其中 $k$ 是 $j$ 的子集。

这样我们每次计算 $dp$ 的时候只要枚举上一个的前 $10$ 位，转移 $s$ 的时候枚举后 $10$ 位，复杂度大致是 $O(n2^{\frac m2})$，可以精细分析到更准确的下界 $O(6^{\frac m2})$，空间可以做到 $O(2^m)$。

for (int i=0;i<=mx;i++)
{
	if (b[i]==0) continue;
	int A=i>>10,B=i&1023;
	ll res=1;
	for (int j=0;j<1024;j++) if ((j&A)==j) (res+=dp[j][B])%=mod;
	f[i]=val[i]*res%mod;
	for (int j=0;j<1024;j++) if ((j&B)==B) (dp[A][j]+=f[i])%=mod;
	(ans+=f[i])%=mod;
}

按 $|S|$ 顺序

考虑按 $|S|$ 顺序进行 DP 转移，也就是按照 $|S|$ 分成 $m$ 层，每一层一定是从之前的层里转移过来。那么我们只需要做完每一层后做一次 FMT 累计入答案，每次计算 $dp$ 的时候可以直接 $O(1)$ 计算，这样时间可以做到 $O(m^22^m)$，空间可以做到 $O(2^m)$。

for (int i=0;i<=m;i++)
{
	for (int j=0;j<(1<<m);j++) dp[j]=0;
	for (int j=0;j<(1<<m);j++)
	{
		if (__builtin_popcount(j)!=i) continue;
		dp[j]=(1+s[j])*val[j]%mod;
		(ans+=dp[j])%=mod;
	}
	FMT();
}

FMT 同时转移（官方做法）

考虑我们执行 FMT 的过程，比方说在做完前 $k$ 位的时候我们得到的数组是什么：$s_i$ 是需要满足前 $k$ 位是 $i$ 的前 $k$ 位的子集，$k$ 位以后恰好就是 $i$ 的 $k$ 位以后，这样的位置的和。

我们直接定义 $sdp_{b,i}$ 表示所有 $dp_{x}$ 的和，其中 $x$ 满足前 $k$ 位是 $b$ 的前 $k$ 位的子集，$k$ 位以后恰好就是 $b$ 的 $k$ 位以后。如果我们计算出了 $dp_b$，我们可以在 $O(m)$ 的时间里计算出 $sdp_b$ 的每个位，递推即可。而我们如果得到了所有 $sdp_x$ 满足 $x<b$，我们也可以 $O(m)$ 计算出 $dp_b$，枚举不同的第一个位置转移即可。

这样可以做到时间 $O(m2^m)$，空间 $O(m2^m)$。

for (int i=0;i<(1<<m);i++)
{
	dp[i]=1;
	for (int j=0;j<m;j++) if (i&(1<<j)) (dp[i]+=s[j][i^(1<<j)])%=mod;
	dp[i]=dp[i]*val[i]%mod;
	s[0][i]=dp[i];
	(ans+=dp[i])%=mod;
	for (int j=1;j<m;j++) 
	{
		s[j][i]=s[j-1][i];
		if (i&(1<<(j-1))) (s[j][i]+=s[j-1][i^(1<<(j-1))])%=mod;
	}
}

分治

考虑对最高位 $0/1$ 分治，也就是在 trie 的结构上做类似 CDQ 分治的东西。那么就是先做左儿子，接下来考虑左儿子对右儿子的贡献，再做右儿子。

考虑记以 $S$ 结束的答案为 $dp_S$，我们还需要在 trie 上一边遍历一边维护 $dp$ 的 FMT 数组 $g$，假设当前做到的位是 $d$，目前已有的数是 $S$，我们需要 $g_i$ 是 $dp_j$ 的和，其中 $j$ 满足满足最高的 $d$ 位和 $i$ 相同，后面的位是 $i$ 子集。那么在每个节点做完左右儿子后，我们把当前子树内的 $g$ 从左儿子向右儿子累加即可。

时间复杂度为 $O(m2^m)$，空间复杂度为 $O(2^m)$。

void solve(int i,int S) 
{
	if (i==-1) 
	{
		Add(g[S],dp[S]);
		return;
	}
	solve(i-1,S);
	for (int T=0;T<(1<<i);T++) Add(dp[S|T|(1<<i)],g[S|T]*val[S|T|(1<<i)]%mod);
	solve(i-1,S|(1<<i));
	for (int T=0;T<(1<<i);T++) Add(g[S|T|(1<<i)],g[S|T]);
}

sol_prob2_platinum_feb23.html
sol_prob2_platinum_feb23.mhtml

By Hdh 2024.11.23

SOSDP P9131 [USACO23FEB] Problem Setting P

人生第一道 Sum over Subsets DP(SOSDP)。
SOSDP 顾名思义，解决的是求 $f(T)=\sum\limits_{S \subset T}g(S)$ 的问题。 首先需要学会最简单的子集枚举。