Stone Game (USACO Gold 2021 February)

Game theory的题，首先要想办法找到Bessie的必胜策略，然后才好统计有多少种方案。

从测试点条件可以看到， $N=2$ 的情况是值得分析的，在纸上反复尝试可以发现， $N=2$ 的时候的Bessie必胜策略，就是在第一次操作之后，让剩下的两堆石头除以 $s_1$ 的倍数一样（有余数没关系），因为这样的情况下，不管Elsie取多少，Bessie都可以在另外一堆里和她取一样多。例如，如果初始石头是 $5，7$ ，除了从第二堆取走 $6, 7$ 显然都可以外，Bessie也可以从第二堆取走 $2$ 个，或者 $3$ 个石头，因为之后剩下的石头是 $s_1$ 的 $2$ 倍和 $1$ 倍（再加余数），所以总方案数是 $4$ 。

用公式表达一下，从 $j$ 堆取 $s_1$ 之后，游戏就变成了 $a'[i] = \lfloor \frac{a[i]}{s1} \rfloor - (i==j)$ 。所以 $N=2$ 时，Bessie必胜的条件，就是 $a'[1]==a'[2]$ 。

推广到更大 $N$ 的时候，我们可以发现，Bessie必胜的条件，是 $a'[i]$ 中每个非零数字都出现偶数次。显然这个依赖于 $\lfloor \frac{a[i]}{s1} \rfloor$ 的奇偶性：

如果有且仅有 $j$ 和 $j-1$ 两个数字出现奇数次，其它都是偶数次，则Bessie只需要从 $\lfloor \frac{a[i]}{s1} \rfloor = j$ 的 $i$ 处任意取走 $s_1$ 个石头，就可以让所有数字都出现偶数次。方案数就是满足此条件的石头堆数量。
如果仅数字 $1$ 出现奇数次，其它都是偶数次，则从这些堆中取走 $s_1$ 就行了。
其它情况，Bessie都没有必胜策略。

剩下的问题，是怎样快速统计奇偶性。直接naive的做除法， $\mathcal{O}(NM)$ ，能得到前一半分。要得到满分，可以用prefix sum，需取 $x$ 次的堆数量，就是包含在 $[xs, (x+1)s-1]$ 范围内的总堆数。复杂度是 $\mathcal{O}(M + \frac{M}{2} + ... + \frac{M}{M})=\mathcal{O}(M \ln M)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n,m;
int a[100005];
int cnt[1000005], ps[1000005], b[1000005];
ll ans;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        m = max(m, a[i]);
        cnt[a[i]]++;
    }
    for (int i = 1; i <= m; i++)
        ps[i] = ps[i-1] + cnt[i];
    for (int s = 1; s <= m; s++) {      // 要取的数
        int tot = m / s;
        int odd = 0;
        for (int j = 1; j <= tot; j++) {
            b[j] = ps[min((j+1)*s-1,m)] - ps[j*s-1];
            odd += b[j] & 1;
        }
        if (odd > 2 || odd == 0) continue;  // Bessie loses
        if (odd == 1 && b[1] & 1)       // 一个奇数，则必须是只有1倍s的是奇数
            ans += b[1];
        else if (odd == 2) {            // 两个相邻的奇数，则从大里面取走一个，都变成偶数
            for (int j = 2; j <= tot; j++)
                if ((b[j] & 1) && (b[j-1] & 1))
                    ans += b[j];
        } 
    }
    printf("%lld", ans);
    return 0;
}