讲课：博弈和构造
对称博弈：
n个硬币围成一圈，每人每次取走一个或两个相邻硬币，取完者胜。
解：n<=2 先手胜，否则先手必败（先手会把圆变成一条链，后手把它变成两个相同的链，然后后手的操作和之前先手操作一致，这样最后取光的操作一定是后手进行的）

巴什博弈：
一堆石子，两人轮流每次取1、2、3颗，取光者胜。
0必败态--1、2、3必胜态--4必败态--5、6、7必胜态....以此类推
n%4==0是后手必胜，否则先手必胜
只能取m~k个：n%(m+k)==0后手必胜
每次只能取2的幂次个（1\2\4\8....）：n%3==0先手败

NIM博弈:
3堆石子，每次可选任一堆去任意多个
(0,0,0)必败
(0,0,x)必胜
(0,x,y)---参考对称博弈
推广：假设异或和为k，一定存在一个>=k的数ai，使得ai^k<=ai,取走使异或和为0即可。

图上博弈：
DAG：有向无环图
sg(x) = mex{sg(y)|y属于F(x)} /// mex：最小的不属于这个集合的整数

CF 1537D
数字n每次减去他的一个因子（1和n除外）
解：1和质数必败
奇数 * 奇数 = 奇数
偶数 * 奇数 = 偶数
偶数 * 偶数 = 偶数
如果当前是奇数，那么一定没有偶数因子，会变成一个偶数 * 一个奇数的形式，相当于提供给对方一个偶数因子，直到变成质数（先手必败）
如果当前是偶数，那么找到一个奇数因子，使其变成奇数（先手必胜）
get(√)

#include <bits/stdc++.h>   
///打表的程序，可以发现奇数必败，偶数形式为2^k时(k是奇数）必败
using namespace std;

int vis[10100],pri[10100],f[10100];
int tot;

void init()
{
    vis[2] = 0;
    for(int i = 2;i <= 10000; ++i)
    {
        if(!vis[i])
        {
            pri[++tot] = i;
           // cout<<i<<endl;
        }
        for(int j = 1;j <= tot && pri[j] * i <= 10000; ++j)
        {
            vis[pri[j] * i] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}

int fi(int x)
{
    if(!vis[x]) return 0;
    for(int i = 2;i * i <= x; ++i)
    {
        if(x % i == 0 && f[x - i] == 0) return 1;
        if(x % i == 0 && f[x - x / i] == 0) return 1;
    }
    return 0;
}

int main()
{
    init();
    f[1] = 0;
    for(int i = 2;i <= 10000; ++i) f[i] = fi(i);
    for(int i = 2;i <= 10000; i += 2)
        if(f[i] == 0) cout<<i<<endl;
    return 0;
}

n堆石子，每次从不超过k堆中取任意多个石子，最后不能取的人失败。
解：n堆石子的石子数用二进制表示，统计每个二进制位上1的个数，若每一位上1的个数mod(k+1)全部为0，则必败，否则必胜。

证明：
1.全为0的局面一定是必败态。
2.任何一个P状态，经过一次操作以后必然会到达N状态：在某一次移动中，至少有一堆被改变，也就是说至少有一个二进制位被改变。由于最多只能改变k堆石子，所以对于任何一个二进制位，1的个数至多改变k。而由于原先的总数为k+1的整数倍，所以改变之后必然不可能是k+1的整数倍。故在P状态下一次操作的结果必然是N状态。
3.任何N状态，总有一种操作使其变化成P状态。从高位到低位考虑所有的二进制位。假设用了某种方法，改变了m堆，使i为之前的所有位都回归到k+1的整数倍。现在要证明总有一种方法让第i位也恢复到k+1的整数倍。
有一个比较显然的性质，对于那些已经改变的m堆，当前位可以自由选择1或0.
设除去已经更改的m堆，剩下堆i位上1的总和为sum
分类讨论：
(1)sum<=k-m,此时可以将这些堆上的1全部拿掉，然后让那m堆得i位全部置成0.
(2)sum>k-m 此时我们在之前改变的m堆中选择k+1-sum堆，将他们的第i位设置成1。剩下的设置成0.由于k+1-sum<k+1-(k-m)<m+1,也就是说k+1-sum<=m，故这是可以达到的。

反nim游戏
一个状态为必胜态，当且仅当：
　　1）所有堆的石子个数为1，且NIM_sum=0
　　2）至少有一堆的石子个数大于1，且 NIM_sum≠0

构造

数字型
1）CF468C
对于a，求l,r使得l的r的所有数位和的和mod a == 0
a<=1e18,1<=l<=r<=1e200
2）双拆分数
可以发现对于n位的数字，可以由n-2位的加两个0得到，比如1144合法，110440和114400都合法
n<=3无解
只要找到n=4和n=5的一个解就可以

序列型