《博弈

green博弈：

模型：对于一棵树，两个人A和B每次可以选定一个点删去，同时这个点的子树也会被删去。

考虑必胜态和必败态的判断。

首先如果是一条链，那么就可以看成取一堆石子。

那么，从根上再延伸出一条链，那么就可以看成取两堆石子，那么就是标准的NIM博弈。

我们知道NIM博弈的答案就是SG函数值，也就是多个堆的异或和。

那么这里我们就可以推出根的SG函数值就是它的子树的SG函数的异或和。

也由上面推导可见，我们根的SG函数和自身没关系，所以对于每个节点的SG函数，初始值应该为0。

在处理子树的时候，再和每个子树加上1。

https://ac.nowcoder.com/acm/contest/16832/J

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e6 + 5;
const int M = 1e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
}
using namespace FASTIO;

vector<int> G[N];
int sg[N];
void dfs(int u,int fa) {
    sg[u] = 0;
    for(auto v : G[u]) {
        if(v == fa) continue;
        dfs(v,u);
        sg[u] ^= (sg[v] + 1);
    }
}
int main() {
    int ca;ca = read();
    while(ca--) {
        int n;n = read();
        for(int i = 1;i <= n;++i) G[i].clear();
        for(int i = 1;i < n;++i) {
            int x,y;x = read(),y = read();
            G[x].push_back(y);
            G[y].push_back(x);
        }
        dfs(1,0);
        printf("%s
",sg[1] ? "NO" : "YES");
    }

   //  system("pause");
    return 0;
}

View Code

nimk博弈：

尼姆博弈是n堆，每次可以一堆取若干个。nimk博弈是nim博弈的扩展，即对于n堆，每个可以选择最多不超过k堆，取若干个。

解：我们对这n堆的石子数量二进制拆分，若对于每个二进制位，所有堆相加%(k + 1)都满足 = 0.

那么先手必败，反之必胜。

https://darkbzoj.tk/problem/4550。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 2e5 + 5;
const int M = 2e3 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;

/*
主要就是求必败态的方案数：
利用dp[i][j] - 表示从高位开始二进制位到i位，用了j个石子，也就是插入了j个1的方案数。
我们需要每一位的1的个数都是(d + 1)的倍数,所以对于每一个二进制位，都枚举(d + 1)的倍数x.
对于这x * (d + 1)个1，我们可以放在这k / 2堆中个任意位置。所以方案数为C(k / 2,x * (d + 1)).
最后对于每种必败态，它的方案数还需要乘上黑白色的排列方案数，因为此时先手已经必败，黑白色的排列不再影响答案。
排列方案数为，黑色可以摆放的方案数或白色，总共n个位置用了i个，另一种颜色占k / 2个，所以是C(n - i - k / 2,k / 2).
*/
LL dp[25][10005],f[10005];
LL ADD(LL a,LL b) {
    return (a + b) % Mod;
}
LL quick_mi(LL a,LL b) {
    LL re = 1;
    while(b) {
        if(b & 1) re = re * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return re;
}
void init() {
    f[0] = 1;
    for(int i = 1;i < 10005;++i) f[i] = f[i - 1] * i % Mod;
}
LL C(LL n,LL m) {
    return f[n] * quick_mi(f[m],Mod - 2) % Mod * quick_mi(f[n - m],Mod - 2) % Mod;
}
int main() {
    init();
    int n,k,d;scanf("%d %d %d",&n,&k,&d);
    int up = n - k;
    dp[0][0] = 1;
    for(int i = 0;i < 20;++i) {
        for(int j = 0;j <= up;++j) {
            for(int x = 0;x * (d + 1) <= k / 2;++x) {
                LL ma = j + 1LL * x * (d + 1) * (1 << i);
                if(ma > up) break;
                dp[i + 1][j + x * (d + 1) * (1 << i)] = ADD(dp[i + 1][j + x * (d + 1) * (1 << i)],dp[i][j] * C(k / 2,x * (d + 1)) % Mod);
            }
        }
    }
    LL ans = C(n,k);//所有方案数
    for(int i = 0;i <= up;++i) {
        ans = ans - dp[20][i] * C(up + k / 2 - i,k / 2) % Mod;
        ans = (ans + Mod) % Mod;
    }
    printf("%lld
",ans);
    system("pause");
    return 0;
}

View Code