CF1312F Attack on Red Kingdom

发表于 | 阅读数

有 $n$ 个数，第 $i$ 个为 $a_i$
有甲、乙两人轮流操作，甲先操作。
一次操作有 3 个选项：

  • 将一个大于 $0$ 的数减 $x$
  • 将一个大于 $0$的数减 $y$
  • 将一个大于 $0$ 的数减 $z$

如果操作后该数小于 $0$ ,则变为 $0$.

SG函数是个值！

这里就是有向图$SG$函数。

然后枚举操作，让对方必败即可。

但是这里$n$太大了。

打表可以知道有循环节。

设 $𝑓(𝑖,𝑗)$ 表示$𝑖$个人，上一次操作是 $𝑗$ 的SG值。那么若 $𝑓(𝑖)∼𝑓(𝑖+4)$ 与之前的五行重复了，则$𝑓(𝑖+5)$ 一定与之前的五行的下一行一样。

用点技巧找到循环节即可。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
#define ll long long

vector<int> x(3);

int mex(int a, int b, int c)
{
    vector<int> vis(5);
    vis[a] = vis[b] = vis[c] = 1;
    for (int i = 0; i <= 3; i++)
        if (!vis[i])
            return i;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        vector<vector<int>> dp(200, vector<int>(3));
        cin >> n >> x[0] >> x[1] >> x[2];
        int cycst = 1, cyclen = 1;
        map<vector<array<int, 3>>, int> mp;
        for (int i = 1; i < 200; i++)
        {
            dp[i][0] = mex(dp[max(0, i - x[0])][0], dp[max(0, i - x[1])][1], dp[max(0, i - x[2])][2]);
            dp[i][1] = mex(dp[max(0, i - x[0])][0], 4, dp[max(0, i - x[2])][2]);
            dp[i][2] = mex(dp[max(0, i - x[0])][0], dp[max(0, i - x[1])][1], 4);
            //cout << dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << " " << i << endl;
        }

        auto init = [&]() {
            vector<array<int, 3>> tmp(30, {0, 0, 0});

            for (int i = 1; i < 100; i++)
            {
                mp[tmp] = i;
                tmp.erase(tmp.begin()), tmp.push_back({dp[i][0], dp[i][1], dp[i][2]});
                if (mp.count(tmp))
                {
                    cyclen = i - mp[tmp] + 1, cycst = mp[tmp] + 1;
                    return;
                }
            }
        };
        init();
        auto SG = [&](ll i, int j) {
            if (i <= 0)
                return 0;
            if (i < cycst)
                return dp[i][j];
            return dp[cycst + (i - cycst) % cyclen][j];
        };
        // cout << cycst << " " << cyclen << endl;
        vector<ll> a(n + 1);
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        ll sg = 0;
        for (int i = 1; i <= n; i++)
            sg ^= SG(a[i], 0);
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            sg ^= SG(a[i], 0);
            for (int j = 0; j <= 2; j++)
            {
                if (!(sg ^ SG(a[i] - x[j], j)))
                    ans++;
            }
            sg ^= SG(a[i], 0);
        }
        cout << ans << endl;
    }
}