题解：CF1312F Attack on Red Kingdom
可以等价成类似 nim 游戏，进攻就像取石子，取走最后一颗石子的一方获胜。
同时由于所有城堡独立，可以考虑 SG 函数。
所以基本思路就是枚举第一次操作是什么然后算出这种情况下的 SG 函数值看是否必胜。
问题是此题每堆石子数量非常巨大没法直接算 SG 函数，但是我们发现几乎一定有循环节所以写个暴力找到循环节就行了。
代码
这是重头戏（这次是真的！因为我代码里的致死量注释保证理解每一行代码）。
/*
the essential constraint that allows us to
quickly find the loop knot is the fact
that x, y, z <= 5 so we will only
use the last 5 rows
*/
#include<bits/stdc++.h>
#define INF 1000000000000005
#define int long long
using namespace std;
int t;
int n, X, Y, Z, a[300005], cnt, sz, ans;
typedef vector<vector<int> > sta;
//this is a state of the sg function
//sg[i][j] meaning a castle with i
//士兵 remaining and the last attack
//being type j
sta looplog;
//keeping track of the values of
//all sg function <= the loop knot
int mex(vector<int> x){
//umm do i need to explain how to find the mex
//of a vector???
for(int i = 0; i <= x.size(); i++){
int check = 0;
for(auto j: x)if(j == i)check = 1;
if(check)continue;
return i;
}
return 0;//yeah umm
}
void loop_knot(){
//gotta find the loop knot first
map<sta, int> d;
d.clear();
//wheter this combination of the
//5 rows of vectors existed before
//specifically each d keep track of
//5 rows in the sg table each with
//3 columes the 5 rows represent
//the number of 士兵 left from
//i to i - 5 and columes are for the
//type of the last move made
sta cur(3, vector<int>(5, 0));
//meaning cur is 3 vectors each with
//5 0s in it
//this is the initial vector just
//like i said, cur[0, 1, 2] each
//represent a colume with 5 elements in each
//of them meaning the value of the sg
//function for i, i - 1, i - 2 ... i - 5 士兵
//in a castle
cnt = 0;
//if there are cnt 士兵 in a castle
looplog.clear();
while(!d.count(cur)){
//while cur haven't existed
//yet we continue computing later
//curs, but if it has, we know
//it MUST go into a cycle because
//we ONLY use the last 5 rows
//when transfering the sg function
d[cur] = cnt;
//cur first existed for the sg
//function of a castle with cnt 士兵
looplog.push_back({cur[0].back(), cur[1].back(), cur[2].back()});
//the bottom of each of the columes aka the
//last row, is the value of the sg function if
//u launch an attack of type 0 1 or 2 on a castle
//with cnt 士兵 remaining
//compute the new cur value
sta nw = cur;
nw[0].push_back(mex({cur[0][5 - X], cur[1][5 - Y], cur[2][5 - Z]}));
nw[1].push_back(mex({cur[0][5 - X], cur[2][5 - Z]}));
nw[2].push_back(mex({cur[0][5 - X], cur[1][5 - Y]}));
//for each colume, we add another number to it meaning
//if we had 1 more soldier in the castle and we
//last did move 0/1/2 on it
//5 - X/Y/Z is because we're currently at colume
//5 which means the sg function for cnt 士兵 being in
//the castle, so the sg function of cnt + 1 士兵
//is just cnt + 1 - X/Y/Z(depending on which move)
//which is just 5 - X/Y/Z(depending on which move)
//for cur, and taking mex is just cuz that's
//the def of sg function
nw[0].erase(nw[0].begin());
nw[1].erase(nw[1].begin());
nw[2].erase(nw[2].begin());
//we only need to keep 5 rows because the
//earlier rows won't ever be used for transfering
//so we erase the first row after each time we
//increase a soldier
cur = nw;
cnt++;
//now we consider the case where there is 1 more
//soldier in the castle
}
sz = cnt - d[cur];
// cout<<cnt<<" "<<d[cur]<<" "<<sz<<endl;
//sz = the size of each loop, because
//we know we ended after cnt 士兵 but
//that's not the size of the loop knot
//unless cur is also the first state to appear
//but if it isn't the size of the loop knot is
//just the second time cur appeared(which is cnt) - first
//time which is just d[cur]
}
//alright good job u just walked through the most
//difficult part of this problem with me, now that
//we found the loop knots' size and kept track of all
//values <= loop knot in looplog we can O(1) caluclate
//the sg function value for any sg[x][y] meaning
//a castle with x 士兵 left and last attack being type y,
//by just doing the following =
int sg_function(int x, int y){
// cout<<x<<" "<<y<<endl;
if(x < cnt){
//from 0 to cnt is before
//any value appeared more than once
//they're also the spots that are recorded
//DIRECTLY in log
return looplog[x][y];
}
// cout<<" "<<sz<<endl;
x -= (cnt - sz);
//cnt - sz is the number of elements
//that are not in the loop, the elements that
//appeared before the first loop element appeared
int tmp = (cnt - sz) + (x % sz);
//x % sz = to which element in the loop have we
//reached, + (cnt - sz) because we need to add
//back the first unlooped elements
// cout<<tmp<<endl;
return looplog[tmp][y];
}
signed main(){
cin>>t;
while(t--){
cin>>n>>X>>Y>>Z;
//x = mixed
for(int i = 1; i <= n; i++){
cin>>a[i];
}
loop_knot();
//first we find the loop knot
// cout<<"preprocessdone "<<sz<<endl;
int orig = 0;
for(int i = 1; i <= n; i++){
// cout<<i<<endl;
orig ^= sg_function(a[i], 0);
//if we don't do any attack
//on any castle the value
//is obviously sg[a[i]][0] bc
//0 doesn't bring any restrictions
//on the next attack and a[i]
//means it's not yet attacked
}
// cout<<"sgfunction no problem"<<endl;
ans = 0;
for(int i = 1; i <= n; i++){
orig ^= sg_function(a[i], 0);
//if we don't not do an attack on
//castle i instead what if
//we do a type 0/1/2 attack?
ans += (orig == sg_function(max(0LL, a[i] - X), 0));
ans += (orig == sg_function(max(0LL, a[i] - Y), 1));
ans += (orig == sg_function(max(0LL, a[i] - Z), 2));
//only when they're equal would they xor to 0
//which is a must lose condition for the black
//king who is about to make move next
orig ^= sg_function(a[i], 0);
//add it back
}
cout<<ans<<endl;
}
return 0;
}