进入正题
1004
这道题没写出来最后，但依然有所收获。正如题解所说，像这种一大堆操作得到某种符合设定的东西，然后进行计数的题，往往都需要一个简洁的性质。这种性质不是手模样例搞出来的，就是猜出来的。但是像我这种蒟蒻，脑电波不容易对上的，模又模不出来，猜也猜不对，拿到一个题根本无法下手。但是这个1004，却给了我一种新的思考方式：从设定推出性质，使得这种性质能够连接操作和最后的设定。更具体的说，设操作为A，设定为C，我们需要某种性质使得A->B->C且C->B。手模样例得到性质，或许就是A->B的过程；而猜结论，或许是B->C再检验是否符合操作的过程。这样还剩下的一种解法是C->B。即直接从设定入手找到设定C成立的充要条件且能与A相联系。
比如这个1004，可以从最后的设定入手。这个设定有什么性质？
首先是\([Min,Max]\)的数每个都有一个，这个是个充要条件，对吧？但是好像很难利用。
第二个性质是这个集合里的数的和一定能算出来，等差数列嘛。在操作的过程中，\(Max\)和\(Min\)肯定是不变的，那我找到了最值就能求和，但是真的能利用这个性质吗？和一定的时候它的集合一定是我们想要的吗？简单证明一下发现成立；
第三个性质是差分数组满足特殊性，构成是\(Min、1、1、1……\)。而对两个数进行操作能够减小他们之间的差值。我通过手写样例发现，每次操作两个数可以让差变成两个一半，比如数列{2，6}，差分数组是{2，4},操作后变成{2，2，2}，又可以继续操作，变成{2，1，1，1，1}。至此，我们得到了题解中提到的“最终目标就是将差分数组变为全是1 。那么如果相邻的\(a_{i}-a_{i-1}\)都是2的次幂，那么答案显然为 Yes”。这个过程中也发现了另外一个结论，两个奇偶性相同的数，差值一定为偶数(超级好证明)。但是此时又会发现我上面的操作都是对相邻的两个奇偶性相同的数进行操作，如果不相邻勒？这个时候就是题解中提到的特殊情况了。我推到这里就没法往后推了，遂看题解。但是题解里来了一句“不难发现”，这可很难发现啊！！！这种特殊情况是如何量化到gcd上，gcd又是如何能代表所有情况，好像真的需要点脑电波。不过我没有QWQ;
其实哔哔了这么多，说的还是一个事情，拿到这种题不知道怎么下手的时候，可以从设定推设定具有的性质，然后再考虑这些性质能推出来什么。好吧，其实可能像这个1004一样很难往下推，但是起码有个方向不是？
1007
在杭电第二场的博弈论中，我学会了SG函数打表，SG值为0时，先手必败，反之先手必胜。（附上那道题的打表代码）
int sg[100][100];int init(int a,int b){if(sg[a][b]!=-1) return sg[a][b];set<int>s;for(int k=1;k<=3;k++){if(a>=k)s.insert(init(a-k,b));}if(b>=1){s.insert(init(a+1,b-1));s.insert(init(a,b-1));if(a>=1)s.insert(init(a-1,b-1));}if(b>=2){s.insert(init(a+1,b-2));}for(int i=0;;i++){if(!s.count(i)){return sg[a][b]=i;}}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);memset(sg,-1,sizeof(sg));for(int i=1;i<=10;i++){for(int j=1;j<=10;j++){init(i,j);}}for(int i=1;i<=10;i++){for(int j=1;j<=10;j++){cout<<sg[i][j]<<" ";}cout<<endl;}return 0;
} 但是SG函数有个缺陷，就是博弈最后一定有人赢有人输，不会像这道题一样平局(如果出现平局了SG函数会一直递归，没办法终止)。或许我们可以设定一个递归次数？递归10000次还没结束就说明是平局？感觉能行，这个时候我就可以不用SG函数了，都是递归，直接dfs去搜吧。但是怎么确定这里的10000？递归次数多了会爆，少了答案又不正确，似乎很难。虽然这道题好像还真能确定这个次数，不过我不会。
只能换一种做法了。
博弈论，大多数情况下是一种局面情况转移的过程吧，我们知道必胜策略的时候，我转移的时候就能够采取必胜策略，类似DP；我们不知道必胜策略的时候我只能打表推结论；如果两个都不知道，该怎么办？既然是情况的转移，我们就可以把每个情况看作一个节点，每次转移看作一条边，建图，这与SG函数有异曲同工之妙，我的理解是SG函数省掉了建图的过程直接求结果。对于先手，如果一个状态经过操作后能够使局面变成必败态，那轮到后手，后手肯定会输，这个状态称为必胜态(对应的SG值为1)；反之，如果先手操作后只能使局面变成对后手有利的必胜态，那这个状态一定是对先手而言的必败态，注意这里我强调了“只能”，为什么？考虑一个状态既能转移到必胜态也能转移到必败态，如果是你你会怎么做？显然是采取最优策略，操作后转移到必败态给后手造成最劣局面而不是转移到必胜态让对手去win，那么这种状态依然是必胜态。所以我们在定义必胜态的时候，说的是操作后只要能够使局面变成必败态，那它就是必胜态；而只能让局面变成必胜态就是必败态。当我定义完所有的必胜态必败态后，没被定义的就是平局了。总结一下：
1.如果一个状态操作后能转移到必败态，那么该状态是对先手而言的必胜态；
2.如果一个状态操作后只能转移到必胜态，该状态对先手而言是必败态；
3.未被定义的状态是平局，一定能在有限操作结束游戏的背景下不会出现平局。
那么回归做题，写代码的时候我们对每种情况编号，抽象成节点，用一个队列存放所有已知状态的节点，比如这道题，\(a_{x}=0,a_{y}=0\)时，该节点A赢,已知状态，我就把它放到队列中。我们可以在给情况赋编号的时候将这类已知状态的点先放入队列中，类似拓扑排序中刚开始入度为0的点。然后我们建边。建边是根据博弈的规则建边的，比如A操作时是\([a_{x}][a_{y}][b_{x}][b_{y}]\),轮到B时或许就变成了\([b_{x}][b_{y}][(a_{x}+b_{x})\% 10][a_{y}]\)，我们把这两个节点建一条单向边（更细节的是这个数组的前两维放的是当前操作者手上的数,比如A操作时前两维放\(a_{x},a_{y}\)，B操作时前两维放\(b_{x},b_{y}\) )。每次从队列中取出节点，由于这些节点是知道状态的，所以就能利用上面的规则去更新能到达这个节点的节点的状态。但是我们建图方式只能知道当前节点能到达哪些节点，不知道哪些节点能到达当前节点。怎么解决？再开一个数组存反向边就行。也就是说我们的正向边是按照博弈规则建立的，我们的反向边是用来推其他节点的状态的。具体看代码，更好理解：
const int N1=11;
const int N2=2e5+10;int id[N1][N1][N1][N1],idx;//编号int ans[N2];//存节点的答案vector<int>e[N2];//正向边
vector<int>re[N2];//反向边int cnt[N2];void init(){queue<int>q;//对列，存已知状态的点for(int a=0;a<=9;a++){for(int b=0;b<=9;b++){for(int c=0;c<=9;c++){for(int d=0;d<=9;d++){id[a][b][c][d]=++idx;//所有情况量化成节点if(a==0&&b==0){ans[idx]=1,q.push(idx);//已知状态放入队列作为遍历的起点}else if(c==0&&d==0){ans[idx]=2,q.push(idx);}}}}}auto add=[&](int u,int a,int b,int c,int d)->void{int v=id[c][d][a][b]; e[u].push_back(v);re[v].push_back(u);};//建边for(int a=0;a<=9;a++){for(int b=0;b<=9;b++){for(int c=0;c<=9;c++){for(int d=0;d<=9;d++){//根据规则建边int u=id[a][b][c][d];if(a!=0){if(c!=0) add(u,(a+c)%10,b,c,d);if(d!=0) add(u,(a+d)%10,b,c,d);}if(b!=0){if(c!=0) add(u,a,(b+c)%10,c,d);if(d!=0) add(u,a,(b+d)%10,c,d);}}}}}while(!q.empty()){int x=q.front();q.pop();//若当前点为必胜态if(ans[x]==1){//利用反向边找到哪些点能到当前点xfor(auto y:re[x]){//已经判断过状态的点跳过，反之检查if(ans[y]==0){cnt[y]++;//记录当前点能到达多少个必胜态if(cnt[y]==e[y].size()){ans[y]=2;q.push(y);//更新状态并入队}//cnt[y]=e[y].size(),说明y能到达的点全是必胜态，对应结论一个点只能到达必胜态则是必败态}}}else{for(auto y:re[x]){//已经判断过状态的点跳过，反之检查if(ans[y]==0){ans[y]=1;q.push(y);}//只要能到必败态，那他就是必胜态，也是对应的结论}}}//只有必胜态和必败态入队，没入队的就是平局了
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);init();int T;cin>>T;while(T--){int a,b,c,d;cin>>a>>b>>c>>d;cout<<ans[id[a][b][c][d]]<<endl;}return 0;
}
追更
1010
从昨天晚上想到现在，不得不说这是一个很好的图论题；
求一个有向无环图上两个点之间的路径数，一般有三种做法，拓扑排序，bfs ，反向建图dfs+记忆化搜索。所以我拿到这个题的第一想法就是把图搞出来，然后再求路径数。但是这样肯定是对下标\(i\)建图。这就有一个问题，我在遍历每个无序对的时候，需要知道有哪些下标上的数是\(a_{i},a_{j}\)。这个过程可以在输入的时候预处理，\(a_{i}.push\_back(i)\)就行。也就是说把每一个\(a_{i}\)看作一个群体，这个群体下有若干个下标使得该下标上的元素是\(a_{i}\),也可以理解成题解说的“颜色”。处理的时候遍历群体\(a_{i}\)与\(a_{j}\),枚举\(a_{i}\)中的每一个数字，与\(a_{j}\)中比它大的数字连边。由于是无序对，所以还需要用同样的方式处理\(a_{j}\)。时间复杂度明显来到了平方级别。更细节的。假设\(m=1\)，无序对是1和2，数组的左半部分是1，右半部分是2，此时，每一个1都要和右边的2连边，是\(\frac{n}{2}\)条边，那有\(\frac{n}{2}\)个1，一共就是\(\frac{n^{2}}{4}\)条边，这个稠密度显然没办法用拓扑排序或者搜索去求路径数。于是我得到了第一个猜想，不能直接对下标进行连边。
手模样例。遍历到\(i=2\)时需要加上\(i=1\)对\(i=2\)的路径数贡献，遍历到\(i=3\)时需要加上\(i=1\)和\(i=2\)对\(i=3\)的路径数贡献。或者说，我遍历到\(i=1\)时就把1对后继节点的贡献提前给他算好，但是你总不能遍历所有\(i=1\)的子节点吧，图都建不了。不过后面的\(i=2\)和\(i=4\)都是属于群体\(a_{i}=2\)，1对这个群体都产生了贡献，而这些群体又是\(a_{1}\)的子节点！！！这说明，可以对\(a_{i}\)连边。
深入思考，设\(ans[i]\)为以1为起点,i为终点的路径数，\(f[j]\)为前面节点对j产生的贡献，固有代码：
for(int i=1;i<=n;i++){ans[i]+=f[a[i]];//到达i的路径数为前面的节点对a[i]产生的贡献for(auto j:e[a[i]]){f[j]+=ans[i];//节点i对a[i]的后继节点产生的贡献}
}
感觉有点绕，对着样例思考这个代码其实很容易理解
但是，这个代码的复杂度是不可接受的，第一维是n，第二维受到e[a[i]]的节点数决定。如果e[a[i]]的节点数比较小，是不是就可以接受了，比如\(logn\)或者\(\sqrt{n}\)。如果你熟悉根号分治的话，就知道怎么处理了，所谓的根号分治，无非就是把某个东西分成\(<\sqrt{n}\)和\(>\sqrt{n}\)两个部分，一个直接暴力枚举，复杂度不超过\(\sqrt{n}\)，另外一个预处理。在图论中的根号分治主要是度数根号分治。一个节点的出度，意味着其子节点的数目，比如代码中的\(j:e[a[i]]\)，这样就可以使复杂度可以接受了。但是这样有个问题。我们只算了度数\(<\sqrt{m}\)(m是边数)的节点对后继节点的贡献，但是没算度数\(>\sqrt{m}\)的节点产生的贡献。细想一下，当我遍历到i时，只要知道前面的节点有哪些是度数比根号m大的，就能算出之前没算的贡献。而度数大于根号m的节点数不超过根号m(可以简单证明)，那我是不是可以建反向边，只要一个节点的初度大于根号m，那我就遍历这个节点的所有子节点（由于度数大于\(\sqrt{m}\)的节点个数不超过\(\sqrt{m}\)。这些子节点又是大度数点，所以不超过\(\sqrt{m}\)，平衡了复杂度），然后建反向边，这样在后继处理的时候，我就知道前面有哪些度数比根号m大的节点与这个节点连了边。我补上这一部分贡献，在去算这个点对后继节点的贡献。
vector<int>ans(n+1,0);ans[1]=1;//记录到i的路径数
vector<int>f(c+1,0);//记录来自小度数节点的贡献
vector<int>g(c+1,0);//记录来自大度数节点的贡献for(int i=1;i<=n;i++){ans[i]+=f[a[i]];//先加上前面小度数节点对的贡献for(auto j:re[a[i]]){ans[i]+=g[j];//加上前面大度数节点的贡献，这种节点如果没出现在前面，他的g[j]=0,不影响结果}g[a[i]]+=ans[i];//不管这个节点是不是大度数，先维护，如果是大度数，后继如果遍历某个节点的大度数点有他，就算贡献，没他，计算时不加上他也没影响if(e[a[i]].size()<=B){for(auto j:e[a[i]]){f[j]+=ans[i];//当前节点对后继节点产生的贡献}}
}
上完整代码
const int mod=1e9+7;void solve(){int n,c;cin>>n>>c;vector<int>a(n+1);for(int i=1;i<=n;i++){cin>>a[i];}int m;cin>>m;vector<vector<int>>e(c+1);for(int i=1;i<=m;i++){int u,v;cin>>u>>v;e[u].push_back(v);if(u!=v) e[v].push_back(u);}vector<vector<int>>re(c+1);int B=__builtin_sqrtl(m);for(int i=1;i<=c;i++){if(e[i].size()>B){for(auto j:e[i]){re[j].push_back(i);}}}vector<int>ans(n+1,0);ans[1]=1;vector<int>f(c+1,0);vector<int>g(c+1,0);for(int i=1;i<=n;i++){ans[i]=(ans[i]%mod+f[a[i]]%mod)%mod;for(auto j:re[a[i]]){ans[i]=(ans[i]%mod+g[j]%mod)%mod;}g[a[i]]=(g[a[i]]%mod+ans[i]%mod)%mod;if(e[a[i]].size()<=B){for(auto j:e[a[i]]){f[j]=(ans[i]%mod+f[j]%mod)%mod;}}} cout<<ans[n]<<endl;
}
应用开发(4)—ArkTs开发语言 – 每天进步一点点)
)
)
)
