http://172.20.6.3/Problem_Show.asp?id=1540
之前莫比乌斯反演也写了一道这种找规律分块计算的题，没觉得这么恶心啊。
具体解释看代码。
翻硬币的具体方法就是分别算出每个单个正面朝上的情况的sg函数然后异或。
#include #include #include #include #include #include #include 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 ; }
手机扫一扫
移动阅读更方便
你可能感兴趣的文章
