http://172.20.6.3/Problem_Show.asp?id=1540

之前莫比乌斯反演也写了一道这种找规律分块计算的题,没觉得这么恶心啊。

具体解释看代码。

翻硬币的具体方法就是分别算出每个单个正面朝上的情况的sg函数然后异或。

 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#include<ctime>
using namespace std;
int n,k,w,mx;
int f[][]={};//n/x和n/(n/x)代表的x的sg值,分成两部分使得储存需要的空间开根
//值得注意的是,这两种划分方式分出的x的范围是一定的,大概是数字的性质。
int vis[]={};
int doit(int x,int y){return x==y?x+:y/(y/(x+));}
int main(){
scanf("%d%d",&n,&k);
//暴力代码
/*for(int i=n;i>=1;i--){
int now=0;
for(int j=i+i;j<=n;j+=i){
now^=f[j];vis[now]=i;
}
for(int j=1;;j++){
if(vis[j]!=i){
f[i]=j;
break;
}
}
}*/
/*暴力打表后可以发现这个东西满足规律:
只要n/x(向下取整)相等sg值就相等。
于是就开始了漫长艰辛的分块计算之旅
倒数真有趣
_
| |
| |
_ _| |_ _
| | | | | |
\_________/
*/
mx=(int)sqrt(double(n));
for(int i=;i<=n;i=doit(i,n)){//这里枚举的i从小到大,其实是n/x
int y,now=,z;
for(int j=;j<=i;j=doit(j,i)){//上一层枚举了n/x,这一层用同样的方式枚举他的倍数
y=i/j;//既然用n/x表达,扩大j倍自然是/j。
z=y<=mx?f[y][]:f[n/y][];
vis[now^z]=i;
if((i/y-i/(y+))&)now^=z;
//如果在范围里有偶数个z,那算下一个的范围的时候z就被自己消掉了所以不用算。
}
for(int j=;;j++){//大家喜闻乐见的mex时间
if(vis[j]!=i){
if(i<=mx)f[i][]=j;else f[n/i][]=j;
break;
}
}
}
for(int i=;i<=k;i++){
scanf("%d",&w);int x,ans=;
for(int i=;i<=w;i++){
scanf("%d",&x);
x=n/x;
ans^=x<=mx?f[x][]:f[n/x][];//喜闻乐见的异或时间
}
if(ans)printf("Yes\n");//喜闻乐见的判定时间
else printf("No\n");
}
return ;
}
05-11 19:39