[数论第四节]容斥原理/博弈论/NIM游戏

typedef long long LL;
const int N = 20;
int p[N];
int n, m;

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++ i) cin >> p[i];
    
    int res = 0; //记录答案
    for(int i = 1; i < 1 << m; ++ i){ //遍历2^m-1次，即遍历所有的方案
        int t = 1, cnt = 0; //记录当前p的倍数，以及p的个数
        for(int j = 1; j <= m; ++ j){ //遍历m位，求出当前方案选取的质数及个数
            if(i >> (j - 1) & 1){
                cnt ++ ; //选取了当前位的质数，质数加一
                if((LL)t * p[j] > n){ //判断质数的倍数是否超出范围
                    t = -1;
                    break;
                }
                t = (LL)t * p[j]; //累乘当前位的质数
            }
        }
        if(t != -1){
            if(cnt % 2) res += n / t; //个数质数位奇数，则取加号
            else res -= n / t; //否则取减号
        }
    }
    
    cout << res;
    return 0;
}

• 由两名玩家交替进行
• 在游戏的任意时刻，玩家执行的合法行动与轮到哪名玩家无关
• 不能行动的玩家判负

普通-NIM游戏

• 有 (n) 堆石子，每堆石子个数为 (a_i) 颗，先手和后手每次可以从某堆中拿任意颗石子，最后无法操作的一方判负
• 结论：当每堆石子的异或值 (a_1 wedge a_2 wedge a_3 ···wedge a_n=0) 时 先手必败，否则先手必胜
• 证明：
  • 当 (a_1 wedge a_2 wedge a_3 ···wedge a_n=xneq0) 时 设 (x) 的二进制中最高位的1在第k位，那么 (a_1···a_n) 中至少有一个数的二进制第k位也是1，设该数为 (a_i) 则 (a_i wedge x<a_i) ，让先手在第i堆中取走 (a_i-a_i wedge x) (一定是合法的)颗石子，第i堆还剩下 (a_i wedge x) 颗石子，此时每堆石子的异或值 (a_i wedge a_2 wedge a_3 ··· wedge a_i wedge x···wedge a_n=x wedge x=0)，故先手总是可以将局面变成所有石子异或值为0的情况，所以最后遇到所有石子为0的情况的一定是后手，故后手必败，先手必胜·
  • 当 (a_1 wedge a_2 wedge a_3 ···wedge a_n=x=0) 时 假设先手在第i堆中拿走k颗石子能将剩余石子的异或值不变，则每堆石子的异或值为 (a_1 wedge a_2 wedge a_3 ···wedge (a_i-k)···wedge a_n=a_1 wedge a_2 wedge a_3 ···wedge a_i···wedge a_n=x=0) 异或满足消去律，所以有 (a_i=a_i-k) 故 (k=0) 矛盾，所以先手不可能将当前局面变成异为0的局面，故后手总是异或非0的局面，而后手总是可以将异或非0的局面变成异或为0的局面，因而先手总是会遇到异或为0的局面，最终所有石子为0的局面一定是先手遇到，故后手必胜，先手必败

台阶-NIM游戏

• 有一个 n级台阶的楼梯，每级台阶上都有若干个石子，其中第 i 级台阶上有 (a_i) 个石子(i ≥1)。两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。
• 结论：当奇数台阶上石子的异或值 (a_1 wedge a_2 wedge a_3 ···wedge a_n=0) 时 先手必败，否则先手必胜
• 石子只能从上一台阶往下一台阶拿，最终局面一定是某人把第一台阶上的石子拿到地面后结束，因此考虑奇数台阶石子异或值的情况
• 当先手遇到奇数台阶石子异或值非0时，将某奇数台阶上的若干石子拿到下一台阶后，总是可以将所有奇数台阶上的石子异或值变成0(见普通nim游戏的分析)。此时，后手总是会遇到奇数台阶石子异或值为0的情况
• 当后手从奇数台阶拿x石子放到下一台阶时，奇数台阶石子异或值一定变为非0(见普通nim游戏分析)，此时，先手又可以将异或非0变成异或为0
• 当后手从偶数台阶拿x石子放到下一台阶时，先手可以顺次将下一台阶的x石子放到下下一台阶，保持奇数台阶异或为0的局面，所以后手总是会遇到奇数台阶石子异或值为0的情况，直到最后，后手会遇到第一台阶无石子可拿的情况，后手判负，先手必胜
• 当先手遇到奇数台阶石子异或值为0时，后手可以依据同样的策略使先手比败，后手必胜

集合-NIM游戏

• n堆石子，玩家可以从任意一堆石子中取走石子，但是每次取的石子个数必须在一个已知的集合S中，最后无法操作的人判负
• 结论：当每堆石子的sg异或值 (sg(a_1) wedge sg(a_2) wedge sg(a_3) ···wedge sg(a_n)=0) 时 先手必败，否则先手必胜
• 集合nim与普通nim游戏的最大区别在于，拿走的石子数必须在一个给定的集合S中。
• 对于普通nim游戏，所有石子异或非0的局面总是能够变成异或为0的局面，异或为0的局面总是只能变成异或非0的局面，故而异或为0的局面总是由同一个人遇到，异或非0的局面总是让另一个人遇到，因此一开始通过石子的异或值就能确定谁是赢家。
• 对于集合nim游戏，是否有同一个局面只会让同一个人遇到的情况呢？答案是可以的。将每种局面抽象为一个图中的节点，一个局面可以到另一种局面就连一条有向边，因而每堆石头的取法都可以通过一个图表示，出度为0的节点表示结束局面
• 定义一个sg(x)函数，表示局面x的sg值，该值总是取到达不了的局面中的最小值，结束局面的sg值为0，能到结束局面的局面的值为1，同理，可以反推出每堆石头一开始的sg值
• 可以发现该sg值与普通nim游戏中异或值的情况有相似之处，即sg值为0的局面只能走到sg值非0的局面，sg值非0的局面总是可以走到sg值为0的局面
• 将每堆石头起始节点的sg值异或起来，sg异或值为0则先手比败，sg异或值非0则先手必胜(sg异或值为0的那一方总是遇到sg值异或值为0)
• 代码：

  #include <iostream>
  #include <unordered_set>
  #include <cstring>
  
  
  using namespace std;
  
  const int N = 110;
  const int M = 1e4 + 10;
  int s[N], f[M]; //s[i]存储可以取的石子数，f[i]存储每个状态的sg值，每个状态用当前石子数表示
  int n, k;
  
  //dfs求sg值
  int sg(int x){
      if(f[x] != -1) return f[x]; //记忆化搜索
      
      unordered_set<int> S; //储存可以走到的局面的sg值
      for(int i = 1; i <= k; ++ i){ //遍历所有可以取的石子数量
          int sum = s[i];
          if(x >= sum) S.insert(sg(x - sum)); //将走到的局面的sg值存储
      }
      
      for(int i = 0; ; ++ i) //从小到大遍历可能的sg值
          if(!S.count(i)) //若该sg值是不能达到的sg中的最小值
              return f[x] = i; //取该sg值
  }
  
  int main(){
      cin >> k;
      for(int i = 1; i <= k; ++ i) cin >> s[i];
      cin >> n;
      
      memset(f, -1, sizeof f);//别忘了初始化
      
      int res = 0;
      while(n -- ){
          int h;
          cin >> h;
          res = res ^ sg(h); //起点的sg异或值
      }
      
      if(res) cout << "Yes";
      else cout << "No";
      return 0;
  }
  

拆分-NIM游戏

• 给定 n堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为 0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。
• 结论：==当每堆石子的sg异或值 (sg(a_1) wedge sg(a_2) wedge sg(a_3) ···wedge sg(a_n)=0) 时 先手必败，否则先手必胜
• 补充sg定理：SG 定理适用于 任何公平的两人游戏, 它常被用于决定游戏的输赢结果。计算给定状态的 Grundy 值的步骤一般包括：
  • 获取从此状态所有可能的转换；
  • 每个转换都可以导致 一系列独立的博弈（退化情况下只有一个）。计算每个独立博弈的 Grundy 值并对它们进行 异或求和。
  • 在为每个转换计算了 Grundy 值之后，状态的值是这些数字的mex
  • 如果该值为零，则当前状态为输，否则为赢。
• 由于玩家的操作是拿走一堆石子，放入两堆石子，因此原来一堆石子的局面变成了两堆石子的局面，而这两堆石头是同时出现，所以尽管是两堆石头，但是属于一个局面，由sg定理此局面的sg值 为 sg(x) = sg(x1) ^ sg(x2) (x -> x1 + x2 拿走x，放入x1，x2)
• 代码：

  #include <iostream>
  #include <cstring>
  #include <unordered_set>
  
  using namespace std;
  
  const int N = 110;
  int f[N];
  int n;
  
  int sg(int x){
      if(f[x] != -1) return f[x];//记忆化
      
      unordered_set<int> s;
      for(int i = 0; i < x; ++ i) 
          for(int j = 0; j <= i; ++ j) //避免重复，约定第二堆的数量小于等于第一堆
              s.insert(sg(i) ^ sg(j)); //两个石子为一个局面，由sg定理：两个石子的sg异或值为当前局面的sg值
              
      for(int i = 0; ; ++ i) //选取不存在的最小的自然数
          if(!s.count(i))
              return f[x] = i;            
  }
  
  int main(){
      cin >> n;
      memset(f, -1, sizeof f);
      int res = 0;
      while(n -- ){
          int x;
          cin >> x;
          res ^= sg(x);
      }
      
      if(res) cout << "Yes";
      else cout << "No";
      return 0;
  }