专栏文章

题解：CF2140E2 Prime Gaming (Hard Version)

SSUNCHAOYI废物生成器
CF2140E2题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miny73ii
此快照首次捕获于
2025/12/02 10:17
3 个月前
此快照最后确认于
2025/12/02 10:17
3 个月前
查看原文
E2 跑了 2859 ms，怎么感觉有点蓟县。

E2

在 E1 的基础上，我们考虑一下设计的状态所表示的信息。设 dpi,S,0/1dp_{i,S,0/1} 表示当在 SS 的状态下，这些位置的石头数量均不小于 kk 时，最后的一堆的石头数是否能不小于 kk。
答案统计的时候，枚举 kk 与 ii，表示 nn 堆石头中有 ii 堆的石头数量为 [k,m][k,m]，n−in - i 堆的石头数量为 [1,k−1][1,k - 1]，则 ∑S=02n−1⟦pop_count⁡(S)=i⟧⋅dpn,S,0×(m−k+1)i×(k−1)n−i\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} 表示答案不小于 ii 的合法数量。显然最后一堆石头的数量为 xx 时的贡献会被拆成 1,2,⋯ ,x1,2,\cdots,x 这 xx 个地方的单个 11 的贡献，因此最后的答案为：
∑i=0n∑S=02n−1⟦pop_count⁡(S)=i⟧⋅dpn,S,0×(m−k+1)i×(k−1)n−i\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}
完整代码如下：
CPP
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);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...