ToB企服应用市场:ToB评测及商务社交产业平台

标题: AtCoder Beginner Contest 368（ABC368） [打印本页]

---

作者: 兜兜零元    时间: 2024-8-25 13:52
标题: AtCoder Beginner Contest 368（ABC368）
[ABC368F] Dividing Game

双倍经验。
题意：

有 \(n\) 堆石子，第 \(i\) 堆有 \(a_i\) 颗石子，每次可以拿走恣意一堆石子数量任何数量的棋子，但是要保证拿走之后该堆的石子数量为原来的约数（不能不拿）。
问是先手必胜照旧后手必胜。
\(n,a_i \le 10^5\)。
思路：

发现与 Nim 游戏类似，且全局信息公开，状态有限，故为公平组合游戏。
思量构造必胜状态，设 \(\operatorname{F}(a) = \operatorname{xor}\limits_{i=1}^n \operatorname{f}(a_i)\)，若 \(a_i = \prod\limits_{i=1}^k p_i^{q_i} (p_i \in prime)\)，则 \(\operatorname{f}(a_i) = \sum\limits_{i=1}^k q_i\)。
手玩后容易发现：

• 当 \(\operatorname{F}(a) \ne 0\) 时为必胜态。
  
• 当 \(\operatorname{F}(a) = 0\) 时为必败态。
  

思量证实。

• 当游戏无法进行时，即 \(a = \{1,1,\cdots,1,1\}\) 时，因为 \(1\) 没有质因子，故 \(\operatorname{f}(1)=0\)，因为恣意个 \(0\) 异或都得 \(0\)，故 \(\operatorname{F}(a) = 0\)，该状态为必败态。
  
• 若当前为必胜态，故绝对可以通过一些策略，使得下一个状态为必败态：
  
  
  
  • 定义 \(\operatorname{F}(a)\) 二进制为 \(1\) 的最高位为 \(k\)。
    
  • 则必然有一个 \(\operatorname{f}(a_i)\) 的第 \(k\) 位为 \(1\)。
    
  • 思量令 \(\operatorname{f}(a_i)' \gets \operatorname{f}(a_i) \operatorname{xor} \operatorname{F}(a)\)，因为 \(\operatorname{F}(a)\) 的最高位为 \(k\)，如许就消去了 \(\operatorname{f}(a_i)\) 第 \(k\) 位的值，因为 \(2^i > \sum_{i=0}^{i-1} 2^i\)，故 \(\operatorname{f}(a_i) \operatorname{xor} \operatorname{F}(a) < \operatorname{f}(a_i)\)。
    
  • 现在我们来思量下是否可以取石子使得 \(\operatorname{f}(a_i)\) 变为小于它的任何数，容易发现是可以的，我们可以除掉恣意质因子的恣意次幂。
    
  • 此时 \(\operatorname{F}(a)' = \operatorname{f}(a_1) \operatorname{xor} \operatorname{f}(a_2) \cdots \operatorname{f}(a_i) \operatorname{xor} \operatorname{F}(a) \operatorname{xor} \operatorname{f}(a_{i+1}) \cdots \operatorname{f}(a_n) = \operatorname{F}(a) \operatorname{xor} \operatorname{F}(a) = 0\)。
    
  • 此时的后继状态 \(\operatorname{F}(a)'\) 就是必败态了。
    
  
  
• 若当前为必败态：
  
  
  
  • 即 \(\operatorname{F}(a) = 0\)，即所有 \(\operatorname{f}(a_i)\) 中二进制第 \(j\) 位为 \(1\) 数量为偶数，那么我们无论如何改变，肯定有至少一位的奇偶性发生变化，使得后继状态 \(\operatorname{F}(a)' \ne 0\)，为必胜态。
    
  
  

如许我们证实了只有当 \(\operatorname{F}(a) \ne 0\) 时，先手必胜。
那么可以使用线性筛筛出每个数是被哪个质数给筛掉的，就可以快速求出一个数的所有质因子幂次之和。
时间复杂度为 \(O(N \log W)\)。

上面是给博弈论小白看的，但是如果您对博弈论颇为纯熟，在发现我们可以将一个数的所有质因子幂次之和变为任何比它小的数时，就转化为了以所有质因子幂次之和为石子数的 Nim 游戏。

Code： [code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod)x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(int i=l;i=l;i--)using namespace std;typedef long double lb;typedef double db;typedef unsigned long long ull;typedef long long ll;const ll N=1e5+10;inline ll read(){    ll x=0,f=1;    char c=getchar();    while(c'9'){        if(c=='-')          f=-1;        c=getchar();    }    while(c>='0'&&c A;        }        int g = 0;        for (int i = 0; i < N; i++){                if (A == 1){                        continue;                }                int c = 0;        while(A>1){            A/=F[A];            c++;        }                g ^= c;        }        if (g != 0){                cout =mod)?(x+y-mod)x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(int i=l;i=l;i--)using namespace std;typedef long double lb;typedef double db;typedef unsigned long long ull;typedef long long ll;const ll N=1e5+10;inline ll read(){    ll x=0,f=1;    char c=getchar();    while(c'9'){        if(c=='-')          f=-1;        c=getchar();    }    while(c>='0'&&c

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4