It's all MAGIC
这种题目一般先考虑局面要满足什么条件能必胜,然后根据这个性质来计数。
如果把黑板上的数写成一个集合 \(S\),那么:
- \(\varnothing\) 为必胜态,\(\{1\}, \{2\}\) 显然为必败态,打表发现其他单元素集合都为必胜态;
- 如果 \(\exists x \in S, x \bmod 2 = 1\),\(S\) 为必胜态,因为可以选择模 \(2\) 使 \(S\) 变为 \(\{1\}\);
- 如果 \(\forall x \in S, 2 \mid x\),且 \(\exists x \in S, x \bmod 4 = 2\),\(S\) 为必胜态,因为可以选择模 \(4\) 使 \(S\) 变为 \(\{2\}\);
- 如果 \(\forall x \in S, 4 \mid x\),考虑选择模 \(3\):
- 如果 \(S\) 变为 \(\{1\}\) 或 \(\{2\}\),那么 \(S\) 为必胜态。
- 否则 \(S\) 在模 \(12\) 意义下为 \(\{4, 8\}\),打表发现 \(\{4, 8\}\) 为必败态。如果 \(S\) 不为 \(\{4, 8\}\),考虑选择模 \(12\),那么 \(S\) 为必胜态。
以上我们讨论了 \(\exists x \in S, 12 \nmid x\) 的情况。还剩下 \(\forall x \in S, 12 \mid x\) 的情况。这时候我们发现讨论起来有些复杂了。
接下来就是这题真正 MAGIC 的地方了!发现 \(a_i \le 200\),意味着若 \(\forall x \in S, 12 \mid x\),那么 \(|S| \le \left\lfloor\frac{200}{12}\right\rfloor = 16\)。考虑暴力状压,暴力转移,这样能求出每一个 \(S\) 是必胜态还是必败态。这部分时间复杂度 \(O(2^{16} \times 200 \times 16)\),可以接受。
接下来就是计数了。
- 对于 \(\exists x \in S, 12 \nmid x\) 的情况,只有 \(\{1\}, \{2\}, \{4, 8\}\) 为必败态。容斥,总方案数减去必败态方案数即可。
- 对于 \(\forall x \in S, 12 \mid x\) 的情况,也是暴力状压,枚举每位填什么数。
总时间复杂度 \(O(2^{16} \times 200 \times 16)\)。
code
// Problem: E - Modulo Nim
// Contest: AtCoder - AtCoder Regular Contest 134
// URL: https://atcoder.jp/contests/arc134/tasks/arc134_e
// Memory Limit: 1024 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 210;
const int maxm = (1 << 16) + 50;
const ll mod = 998244353;
ll n, a[maxn], f[maxn][maxm], g[maxm];
ll dfs(int S) {
if (!S) {
return 1;
}
if (g[S] != -1) {
return g[S];
}
int mx = 0;
for (int i = 0; i < 16; ++i) {
if (S & (1 << i)) {
mx = max(mx, 12 * (i + 1));
}
}
for (int x = 1; x <= mx; ++x) {
set<int> st;
for (int i = 0; i < 16; ++i) {
if ((S & (1 << i)) && (12 * (i + 1)) % x) {
st.insert((12 * (i + 1)) % x);
}
}
if ((int)st.size() == 1 && *st.begin() <= 2) {
return g[S] = 1;
} else if ((int)st.size() == 2 && *st.begin() == 4 && *(--st.end()) == 8) {
return g[S] = 1;
}
int T = 0;
bool flag = 1;
for (int t : st) {
if (t % 12) {
flag = 0;
break;
}
T |= (1 << (t / 12 - 1));
}
if (flag && !dfs(T)) {
return g[S] = 1;
}
}
return g[S] = 0;
}
void solve() {
mems(g, -1);
scanf("%lld", &n);
ll all = 1, mul = 1;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
all = all * a[i] % mod;
mul = mul * (a[i] / 12) % mod;
}
ll ans = (all - mul + mod) % mod;
// {1}
ans = (ans + mod - 1) % mod;
// {2}
bool flag = 1;
for (int i = 1; i <= n; ++i) {
if (a[i] < 2) {
flag = 0;
break;
}
}
if (flag) {
ans = (ans + mod - 1) % mod;
}
// {4, 8}
bool all8 = 1;
flag = 1;
ll pw = 1;
for (int i = 1; i <= n; ++i) {
if (a[i] < 4) {
flag = 0;
break;
} else if (a[i] < 8) {
all8 = 0;
} else {
pw = pw * 2 % mod;
}
}
if (flag) {
ans = (ans + mod - (pw - all8 - 1)) % mod;
}
if (*min_element(a + 1, a + n + 1) < 12) {
printf("%lld\n", ans);
return;
}
// multiples of 12
f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int S = 0; S < (1 << 16); ++S) {
if (!f[i - 1][S]) {
continue;
}
for (int x = 0; 12 * (x + 1) <= a[i]; ++x) {
int T = (S | (1 << x));
f[i][T] = (f[i][T] + f[i - 1][S]) % mod;
}
}
}
for (int S = 0; S < (1 << 16); ++S) {
if (dfs(S)) {
ans = (ans + f[n][S]) % mod;
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest Modulo 134atcoder regular contest modulo atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest degree atcoder regular contest builder atcoder regular contest 164 subsegments atcoder regular contest