题解：CF2140E1 Prime Gaming (Easy Version)

· · 题解

E1

首先 m = 1 的时候只有一种全为 1 的情况，答案为 1。

接下来只需考虑 m = 2 的情况。由于 n \le 20，考虑状压。

先钦定从左往右数第 i 堆石头的信息存在长度为 n 二进制从高位往低位数的第 i 位上。由于 c_i = 1/2，我们设二进制某一位为 0/1 表示石头的数量为 1/2。

设 dp_{i,S,0/1} 表示有 i 堆石子，状态为 S 且当前 Alice 为先手/后手的时候最终的那一堆石头的数量是否能为 2。则有转移方程：

\begin{cases} dp_{i,S,0} = \bigvee_{S' \in \mathcal{F}(S)} dp_{i-1,S',1}\\ dp_{i,S,1} = \bigwedge_{S' \in \mathcal{F}(S)} dp_{i-1,S',0} \end{cases}

其中 \mathcal{F}(S) 表示 S 中的某一位去掉以后的状态，这个可以进行预处理。

设 nxt_{S,i} 表示状态为 S 去掉第 i 堆石头时形成的状态。但需要注意，这个状态 S 在二进制下的长度一直是 n，因此即使没有该位置的信息，直接置为 0 即可。由于是从高位往低位存储信息的，因此是形如 \texttt{xxxxoyy} \to \texttt{xxxxyy} 的合并。显然可以分为两个部分合并，写成如下式子（注意 i 下标是 0-base 的）：

nxt_{s,i} = \left( \left\lfloor \frac{S}{2^{n-i}} \right\rfloor \cdot 2^{n-i} \right) + \left( 2 \cdot \left( S \bmod 2^{n-i-1} \right) \right)

也就是等价于如下表达式：

nxt[S][i] = ((S >> (n - i)) << (n - i)) | ((S & ((1 << (n - i - 1)) - 1)) << 1);

最后的答案为 2^n + \sum \limits_{S = 0}^{2^n - 1} dp_{n,S,0}。

代码如下：

void solve ()
{
    int n = read (),m = read (),k = read (),ans = 0;
    vector <int> fl (n);
    for (int i = 1;i <= k;++i) fl[read () - 1] = 1;
    if (m == 1) {puts ("1");return;}
    vector <vector <int>> dp (1 << n,vector <int> (2,0)),ndp (1 << n,vector <int> (2,0)),nxt (1 << n,vector <int> (n + 1));
    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;
    for (int i = 2;i <= n;++i)
    {
        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];
    }
    for (int S = 0;S < (1 << n);++S) ans += dp[S][0];
    printf ("%d\n",ans + (1 << n));
}