题解：CF2140E2 Prime Gaming (Hard Version)

· · 题解

E2 跑了 2859 ms，怎么感觉有点蓟县。

E2

在 E1 的基础上，我们考虑一下设计的状态所表示的信息。设 dp_{i,S,0/1} 表示当在 S 的状态下，这些位置的石头数量均不小于 k 时，最后的一堆的石头数是否能不小于 k。

答案统计的时候，枚举 k 与 i，表示 n 堆石头中有 i 堆的石头数量为 [k,m]，n - i 堆的石头数量为 [1,k - 1]，则 \sum\limits_{S = 0}^{2^n - 1} \llbracket \operatorname{pop\_count}(S) = i \rrbracket \cdot dp_{n,S,0} \times (m - k + 1)^i \times (k - 1)^{n - i} 表示答案不小于 i 的合法数量。显然最后一堆石头的数量为 x 时的贡献会被拆成 1,2,\cdots,x 这 x 个地方的单个 1 的贡献，因此最后的答案为：

\sum \limits_{i = 0}^n\sum_{S = 0}^{2^n - 1} \llbracket \operatorname{pop\_count}(S) = i \rrbracket \cdot dp_{n,S,0} \times (m - k + 1)^i \times (k - 1)^{n - i}

完整代码如下：

void solve ()
{
    int n = read (),m = read (),k = read ();ll ans = 0;
    vector <int> fl (n);
    for (int i = 1;i <= k;++i) fl[read () - 1] = 1;
    vector <vector <int>> dp (1 << n,vector <int> (2,0)),ndp (1 << n,vector <int> (2,0)),nxt (1 << n,vector <int> (n + 1));
    vector <int> cnt (n + 1,0);
    for (int S = 0;S < (1 << n);++S)
        for (int i = 0;i < n;++i) nxt[S][i] = ((S >> (n - i)) << (n - i)) | ((S & ((1 << (n - i - 1)) - 1)) << 1);
    dp[0][0] = dp[0][1] = 0;dp[1 << (n - 1)][0] = dp[1 << (n - 1)][1] = 1;
    cnt[1] = 1;
    for (int i = 2;i <= n;++i)
    {
        for (int j = 0;j <= n;++j) cnt[j] = 0;
        for (int S = 0;S < (1 << i);++S)
        {
            ndp[S << (n - i)][0] = 0,ndp[S << (n - i)][1] = 1;
            for (int j = 0;j < i;++j) 
                if (fl[j]) ndp[S << (n - i)][0] |= dp[nxt[S << (n - i)][j]][1],ndp[S << (n - i)][1] &= dp[nxt[S << (n - i)][j]][0];
        }
        for (int S = 0;S < (1 << i);++S) 
        {
            dp[S << (n - i)][0] = ndp[S << (n - i)][0],dp[S << (n - i)][1] = ndp[S << (n - i)][1];
            int tot = __builtin_popcount (S);
            cnt[tot] = (cnt[tot] + dp[S << (n - i)][0]) % MOD;
        }
    }
    for (int i = 0;i <= n;++i)
        for (int k = 1;k <= m;++k) ans = (ans + qpow (m - k + 1,i) * qpow (k - 1,n - i) % MOD * cnt[i]) % MOD;
    printf ("%lld\n",ans);
}