Codeforces Round 1049 (Div. 2) E2
解题思路
说白了题目就是让我们求
\[\sum_{i = 1}^{m}i \times cnt_i
\]
其中 \(cnt_i\) 的含义是，最后结果为 \(i\) 的初始局面的数量。
要是能以合理的时空复杂度求出 \(cnt_i\) 当然是极好的，但是这看起来就非常困难...
有一个比较常规的转换方式是：
\[\sum_{i = 1}^{m}i \times cnt_i = \sum_{i = 1}^{m} suf_i
\]
其中 \(suf_i\) 的含义是，最后结果大于等于 \(i\) 的初始局面的数量。
为什么可以这样做呢？根据定义我们有：
\[suf_i = \sum_{j = i}^{m}cnt_j
\]
代入到上式可以发现 \(cnt_i\) 正好被计算了 \(i\) 次。
那么如何维护出 \(suf\) 呢，当要计算 \(suf_i\) 时，我们并不关心初始局面每个位置具体是什么数，只关心三个方面：
- 每个数与 \(i\) 的大小关系。
- 有多少个数是大于等于 \(i\) 的。
- 最终的结果是否大大于等于 \(i\)。
根据前两个方面，我们可以将一个初始局面压缩成一个二进制数，二进制数中为 0 的位表示对应的数小于 \(i\)，为 1 的位表示对应的数大于等于 \(i\)。至于如何判断一个局面的最终结果是否大于等于 \(i\)，需要用一点博弈论的知识，对于 Alice 来说，只需要当前状态（局面）存在一个次态的结果是大于等于 \(i\) 的，那么当前状态的最终结果就是大于等于 \(i\) 的，对于 Bob同理。
于是我们可以设计 \(f_{l,u,0/1}\) 表示对于长度为 \(l\) 的局面 \(u\) 且当前是 Bob/Alice 在操作的结果是否大于等于 \(i\)（最后维护出来的 \(f\) 的结果与 \(i\) 的取值无关）。转移就像上面所说的一样。
维护出 \(f\) 之后，我们统计一下有多少包含了 \(x\) 个大于等于 \(i\) 的数的初始局面的结果是大于等于 \(i\) 的，记为 \(cnt_x\)。于是答案就是：
\[\sum_{i = 1}^{m} \sum_{x = 0}^{n} (i - 1)^{n - x}(m - i + 1)^{x}cnt_x
\]
CODE
int c[N];bool f[N + 5][1 << N][2]; // f[i][u][0/1] 对于长度为 i 的初始状态u，以Bob/Alice先手时最终的结果(1:>= k, 0:<k)
int cnt[N + 5];i64 qpow(i64 a, i64 p) {i64 res = 1ll;while (p) {if (p & 1) {(res *= a) %= Mod;}(a *= a) %= Mod;p >>= 1;}return res;
}// 取走 u 的第p个位后得到的状态
int getv(int u, int p) {int mask = (1 << p) - 1;int v = (u & mask);u >>= 1;u &= ~mask;v |= u;return v;
}void solve() {int n = 0, m = 0, k = 0;std::cin >> n >> m >> k;for (int i = 0; i < k; ++i) {std::cin >> c[i];}f[1][0][0] = f[1][0][1] = false;f[1][1][0] = f[1][1][1] = true;for (int i = 2; i <= n; ++i) {for (int u = 0; u < (1 << i); ++u) {auto &Bob = f[i][u][0];auto &Alice = f[i][u][1];Bob = true;Alice = false;for (int j = 0; j < k; ++j) {if (c[j] > i) {break;}int v = getv(u, c[j] - 1);Bob &= f[i - 1][v][1];Alice |= f[i - 1][v][0];}}}for (int i = 0; i <= n; ++i) {cnt[i] = 0;}for (int u = 0; u < (1 << n); ++u) {if (f[n][u][1]) {cnt[std::__popcount(u)]++;}}i64 ans = 0;for (int i = 0; i < m; ++i) {for (int j = 0; j <= n; ++j) {(ans += qpow(i, n - j) * qpow(m - i, j) % Mod * cnt[j]) %= Mod;}}std::cout << ans << '\n';
}