[ARC134E] Modulo Nim

题目翻译

有 $n$ 个数，第 $i$ 个数的范围是 $[1,a_i]$ 且为整数，显然，有 $\prod\limits_{i=1}^{n} a_i$ 种数列。
现在有两人进行博弈，每次操作设最大数为 $X$，选择一个数 $Y \in [1,X]$ 并把所有数 $\bmod Y$。
最大数为 $0$ 的时候操作方胜利。两人均采取最优策略，问有多少种数列满足先手必胜。

前言

补完这题就收工准备打五十连测啦！！
这是非常抽象的博弈题，这也是十天集训 ARC 题单中最复杂的一题，所以放在最后做。

题目分析

先不要管有多少种数列，我们只看对于一个数列它要满足什么性质才能先手必胜。

• 空集是必败态。
• 单元素 $1$ 和 单元素 $2$ 都是必败态，因为你怎么选对手都必胜（最大值 $0$），所以你必败。
• 其他 $\geq 3$ 的单元素集合都是必胜态，因为对于 $x$ 你总是可以选择 $x-1$ 作为模数。

接下来，考虑多元素集合。

• 如果数列中存在至少一个奇数，则可以通过对 $2$ 取模得到若干个 $1$ 构成的集合，后手必败，先手必胜。
• 特判过后，数列中都是偶数。如果存在 $x \bmod 4 = 2$ 的数，则可以通过对 $4$ 取模得到若干个 $2$ 构成的集合，后手必败，先手必胜。

经过了如上的特判，所有数都是 $4$ 的倍数了。试试看 $\bmod 3$？

• 如果 $\bmod 3$ 之后全是 $1$ 或全是 $2$，那么根据上面的讨论先手必胜。
• 否则 $\bmod 3$ 有 $1$ 也有 $2$，这种数在 $[1,12]$ 中只有 $4,8$，所以它们 $\bmod 12$ 后是 $4$ 和 $8$ 构成的集合。
• 打表得对于 $\{ 4,8 \}$ 是先手必败，若先手先 $\bmod 12$，则此时先手必胜。

现在所有数都是 $12$ 的倍数。逝世看 $\bmod \dots$？？？
当然可以分类讨论到值域上界 $200$，但是非常繁琐。

开始玄学了，观察性质发现 $\lfloor \frac{200}{12} \rfloor = 16$，这代表 $[1,200]$ 内只有 $16$ 个 $12$ 的倍数。
这是什么概念？$2^{16}$ 可接受，可以状压了。

讨论了那么多，我们化简一下。

1. 单元素集合 $1$ 和 $2$ 先手必败。
2. $\{ 4, 8 \}$ 先手必败（注意和 $\bmod 12$ 之后的区分）。
3. 剩余的所有数都是 $12$ 的倍数，状压解决，用搜索判断是否是先手必胜。
4. 那如何统计方案数呢？设 $f_{i,S}$ 表示前 $i$ 个数，集合是 $S$，转移即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 215, M = (1 << 16) + 15;
const int mod = 998244353;
int n, a[N];
int dp[M], t[M];
int st[M];
long long ans = 0, res = 0;

int qmi(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (res * 1ll * a) % mod;
        a = (a * 1ll * a) % mod;
        k >>= 1;
    }
    return res;
}

bool dfs(int S) {
    if (st[S] != -1) return st[S];  //记忆化
    bool flag = 1;
    for (int m = 1; m <= 200; m++) {
        set<int> v;
        for (int j = 0; j < 16; j++)
            if (S & (1 << j) && ((j + 1) * 12 % m > 0)) v.insert((j + 1) * 12 % m);
        //{4, 8}，但是 mod 12
        if ((v.size() == 1 && *v.begin() <= 2) || (v.size() == 2 && *v.begin() == 4 && *(--v.end()) == 8)) return st[S] = 1;

        int nxt = 0; bool F = 0;
        for (int j : v) {
            if (j % 12 > 0) { F = 1; break; }
            nxt |= (1 << (j / 12) - 1);
        }
        if (!F && nxt != S) flag &= dfs(nxt);
        if (!flag) return st[S] = 1;
    }
    return st[S] = 0;
}

int main() {
    scanf("%d", &n);
    ans = 1;
    bool flag4 = 1, flag2 = 1;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        (ans *= a[i]) %= mod;
        if (a[i] < 4) flag4 = 0;
        if (a[i] == 1) flag2 = 0;
    }
    if (flag4) {    //全都 >=4，则扣除掉 {4, 8} 的先手必败
        int cnt = 0;
        for (int i = 1; i <= n; i++)
            if (a[i] >= 8) cnt++;   //每个数可以选 4 或 8
        (res += qmi(2, cnt) - (cnt == n)) %= mod;    //不能都选 8
    } else res++;   //全是 1，先手必败
    //统计全为 2
    if (flag2) res++;

    // cout<<ans<<' '<<res<<endl;

    //计算每种状态是否可行
    memset(st, -1, sizeof st);
    st[0] = 1;
    for (int S = 1; S < (1 << 16); S++)
        if (st[S] == -1) st[S] = dfs(S);

    //计算贡献
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int S = 0; S < (1 << 16); S++) {
            for (int j = 0; j < 16; j++) {
                if ((j + 1) * 12 > a[i]) break;
                (t[S | (1 << j)] += dp[S]) %= mod;
            }
        }
        for (int S = 0; S < (1 << 16); S++) dp[S] = t[S], t[S] = 0;
    }

    //计算答案
    for (int i = 1; i < (1 << 16); i++)
        if (!st[i]) (res += dp[i]) %= mod;
    printf("%lld\n", (ans - res % mod + mod) % mod);
    return 0;
}

后记

ARC 45 题完结撒花！！！