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$。则有转移方程：
其中 $\mathcal{F}(S)$ 表示 $S$ 中的某一位去掉以后的状态，这个可以进行预处理。
设 $nxt_{S,i}$ 表示状态为 $S$ 去掉第 $i$ 堆石头时形成的状态。但需要注意，这个状态 $S$ 在二进制下的长度一直是 $n$，因此即使没有该位置的信息，直接置为 $0$ 即可。由于是从高位往低位存储信息的，因此是形如 $\texttt{xxxxoyy} \to \texttt{xxxxyy}$ 的合并。显然可以分为两个部分合并，写成如下式子（注意 $i$ 下标是 0-base 的）：
也就是等价于如下表达式：
1
| 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}$。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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));
}
|
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} [ \operatorname{pop_count}(S) = i ] \cdot dp_{n,S,0} \times (m - k + 1)^i \times (k - 1)^{n - i}$ 表示答案不小于 $i$ 的合法数量。显然最后一堆石头的数量为 $x$ 时的贡献会被拆成 $1,2,\cdots,x$ 这 $x$ 个地方的单个 $1$ 的贡献，因此最后的答案为：
完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| 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);
}
|
