真的不想写这题,感觉这种题出的很怪。
但是今天模拟赛出了,所以我还是写一下吧。
首先我们只关心当前所有数的集合,有多少我们不关心。设这个集合为 \(S\)。
观察样例,感觉可以猜测先手必败的情况很少,那么我们分类讨论一下。
- \(S = \{1\} / \{2\}\):显然先手必败;
- \(S\) 中存在奇数:那么先手可以选择一个 \(2\),此时 \(S = \{1\}\),那么先手必胜;
- \(S\) 中存在 \(a_i \bmod 4 = 2\):先手可以选择一个 \(4\),此时 \(S = \{2\}\),那么先手必胜;
- \(S\) 中同时存在 \(a_i \bmod 3 = 1\) 和 \(a_i \bmod 3 = 2\):首先这样的数在 \([1, 12]\) 内只有 \(4, 8\),分别对应 \(1\) 和 \(2\)。对于 \(S = \{4, 8\}\) 来说,先手必败。枚举所有情况可知。那么对于其它情况来说,先手选取一个 \(12\) 必定能够使 \(S = \{4, 8\}\),于是先手必胜;
- \(S\) 中只存在 \(a_i \bmod 3 = 1\) 或 只存在 \(a_i \bmod 3 = 2\)(可以有 \(a_i \bmod 3 = 0\)):先手选取 \(3\) 即可使得 \(S = \{1\} / \{2\}\),则先手必胜;
- \(S\) 中的所有数都是 \(12\) 的倍数:由于 \(a_i \le 200\),这样的数只有 \(\lfloor\frac{200}{12}\rfloor = 16\) 个,我们可以直接枚举每一种 \(S\) 暴力计算胜负情况。
那么我们发现这里面先手必败的情况只有:
- \(S = \{1\} / \{2\}\);
- \(S = \{4, 8\}\);
- \(S \subseteq \{12k \mid k \in \mathbf N_+\}\) 中的部分情况。
后两者可以通过状压 DP 求出方案数。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205, P = 998244353;
int n, a[MAXN];
bool f[1 << 16], g[1 << 16];
vector<int> mod(vector<int> s, int m) {
vector<int> t;
for (int i : s) if (i % m) {
t.push_back(i % m);
}
sort(t.begin(), t.end());
t.erase(unique(t.begin(), t.end()), t.end());
return t;
}
bool dfs(vector<int> S) {
if (S.empty()) return true;
if (S == vector<int>{ 1 }) return false;
if (S == vector<int>{ 2 }) return false;
if (S == vector<int>{ 4, 8 }) return false;
for (int i : S) if (i % 12) {
return true;
}
int T = 0;
for (int i : S) T |= 1 << (i / 12 - 1);
if (g[T]) return f[T];
g[T] = 1;
for (int i = 1; i <= S.back(); i++) {
if (!dfs(mod(S, i))) {
f[T] = 1;
break;
}
}
return f[T];
}
int h[MAXN][1 << 16];
void add(int &a, int b) {
a += b;
if (a >= P) a -= P;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
// precompute all boards
f[0] = 1;
for (int s = 0; s < (1 << 16); s++) {
vector<int> S;
for (int i = 0; i < 16; i++) if (s >> i & 1) {
S.push_back((i + 1) * 12);
}
dfs(S);
}
// case 1: {1} or {2}
int ans = 0, tot = 1;
int mn = INT_MAX;
for (int i = 1; i <= n; i++) mn = min(mn, a[i]);
ans++;
if (mn >= 2) ans++;
// case 2: {4, 8}
memset(h, 0, sizeof h);
h[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 4; j++) if (h[i - 1][j]) {
if (a[i] >= 4) add(h[i][j | 0b01], h[i - 1][j]);
if (a[i] >= 8) add(h[i][j | 0b10], h[i - 1][j]);
}
}
add(ans, h[n][0b11]);
// case 3: { 12k }
memset(h, 0, sizeof h);
h[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int s = 0; s < (1 << 16); s++) if (h[i - 1][s]) {
for (int j = 0; j < 16; j++) if (a[i] >= (j + 1) * 12) {
add(h[i][s | (1 << j)], h[i - 1][s]);
}
}
}
for (int s = 0; s < (1 << 16); s++) if (!f[s]) {
add(ans, h[n][s]);
}
for (int i = 1; i <= n; i++) {
tot = 1ll * tot * a[i] % P;
}
ans = (tot - ans + P) % P;
printf("%d\n", ans);
return 0;
}
标签:12,return,Nim,int,bmod,ARC134E,add,vector,Modulo
From: https://www.cnblogs.com/apjifengc/p/17207755.html