P9131 [USACO23FEB] Problem Setting P

· · 题解

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

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

\sum_{i=1}^k\binom kii!

可以直接预处理。那么现在我们需要按顺序进行 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]);
}