CF1091H 题解
$\text{Description}$
给定 $n,f$ ,一共有 $n$ 行棋盘。
每行棋盘上有三个棋子,双人博弈,交替操作。
每个人操作前先选定一个数 $d\neq f$ 且 $d$ 是质数或两个质数的乘积。
先手方可以选择一行,然后将该行左边的一个或两个棋子向右移动 $d$ 格;后手方可以选择一行,然后将该行右边的一个或两个棋子向左移动 $d$ 格。
移动时一个棋子不能跨越另一个棋子。
问先手必胜还是后手必胜。
$n\le 10^5$,坐标绝对值 $\le 10^5$。
$\text{Solution}$
每一行都是独立的,所以可以分别求出每一行的 SG 函数值然后异或。
考虑到移动时一个棋子不能跨越另一个棋子,所以三个棋子相对顺序不变。
然后我们发现绝对坐标是没用的,所以移两个棋子等价于移另一个棋子,所以我们固定中间的棋子,问题变为了:有两堆石子,你可以选择任意一堆,然后从中取走 $d$ 个石子,当然要满足条件,先不能操作者失败。
我们先筛出来合法的 $d$,然后考虑求出 $[1,2\times 10^5]$ 内的 SG 函数值。
这一部分可以用 bitset 优化,具体实现细节见代码。
$\text{Code}$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
| #include<bits/stdc++.h> #define REG register #define MAXN 200005 #define Limit 100 using namespace std; inline void read(int& x){ REG int sign=1; static char c; while(!isdigit(c=getchar()))sign=(c^45)?sign:-1;x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48);x*=sign; }
int n,f; int a,b,c;
int SG[MAXN]; int Ans;
bitset<MAXN> NP; int Pr[MAXN],cnt;
bitset<MAXN> Me[Limit+5]; bitset<MAXN> Stp;
inline void Euler(){ NP.set(1); for(REG int i=2;i<=200000;++i){ if(!NP[i]) Pr[++cnt]=i; for(REG int j=1;j<=cnt&&1ll*i*Pr[j]<=200000;++j){ NP.set(i*Pr[j]); if(!(i%Pr[j])) break; } } }
inline void GetStp(){ for(REG int i=1;i<=cnt;++i){ Stp.set(Pr[i]); for(REG int j=1;j<=i&&1ll*Pr[j]*Pr[i]<=200000;++j) Stp.set(Pr[i]*Pr[j]); } Stp.reset(f); }
inline void GetSG(){ Me[0]=Stp; for(REG int i=1;i<=200000;++i){ while(Me[SG[i]][i]) ++SG[i]; Me[SG[i]]|=Stp<<i; } }
inline void Work(){ read(n),read(f); Euler(),GetStp(),GetSG(); while(n--){ read(a),read(b),read(c); Ans^=SG[b-a-1]^SG[c-b-1]; } if(Ans) puts("Alice\nBob"); else puts("Bob\nAlice"); getchar(),getchar(); }
int main(){Work();}
|