相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3576
神犇题解Ⅰ：http://blog.csdn.net/regina8023/article/details/45034045
神犇题解Ⅱ：http://blog.csdn.net/gromah/article/details/27326991
解题报告
这么麻烦的游戏过程，不是找规律就是SG函数来做咯！
然后手玩一下样例，发现这货并没有什么性质的样子
于是考虑SG函数：
因为每一堆石子相互独立，由SG定理可得：
一个石子堆的SG函数等于分开后各堆石子的SG函数的NIM和
于是考虑暴力枚举M。
这样的话，我们就可以在 $ O({n^2})$ 的时间复杂度内解决该问题了
更进一步，我们发现在枚举M的过程中
因为亦或同一个数偶数次相当于没有亦或
所以我们不必枚举所有的M，只需要分奇偶讨论一下就可以了
于是就用莫比乌斯反演经常用到的“下底函数分块”来解决这个问题啦！
时间复杂度：$ O(n\sqrt n )$
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100000+9;
int F,T,n,vis[N],sg[N];
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline int Get_Sg(int w) {
if (w < F) return sg[w] = 0;
else if (~sg[w]) return sg[w];
else if (sg[w] = 0, 1) {
for (int l=2,r,a,b;l<=w;l=r+1) {
r = w / (w / l);
for (int i=l;i<=min(w,l+1);i++) {
Get_Sg(w / i + 1);
Get_Sg(w / i);
}
}
for (int l=2,r,a,b,tmp;l<=w;l=r+1) {
r = w / (w / l);
for (int i=l,tmp=0;i<=min(w,l+1);i++,tmp=0) {
if ((w % i) & 1) tmp ^= sg[w / i + 1];
if ((i - (w % i)) & 1) tmp ^= sg[w / i];
vis[tmp] = w;
}
}
for (int i=0;;i++)
if (vis[i] != w)
return sg[w] = i;
}
}
int main(){
memset(sg,-1,sizeof(sg));
T = read(); F = read();
for (int t=T,vout;t;--t) {
n = read(); vout = 0;
for (int i=1;i<=n;i++)
vout ^= Get_Sg(read());
if (t<=1) printf("%d\n",!vout?0:1);
else printf("%d ",!vout?0:1);
}
return 0;
}
Wow! This blog looks just like my old one! It’s on a entirely different topic but it has
pretty much the same layout and design. Great choice of colors!
Thanks for some other informative website. The place else
could I am getting that kind of information written in such
an ideal manner? I have a venture that I’m simply now
working on, and I have been at the glance out for such info.
Asking questions are genuinely good thing if you are not understanding something totally, except this piece of writing provides fastidious understanding yet.
I have been surfing on-line more than 3 hours today, but I by no means found
any attention-grabbing article like yours. It is lovely price sufficient for me.
In my view, if all website owners and bloggers made just right content as you probably did, the internet will likely
be much more useful than ever before.
I loved as much as you’ll receive carried out right here.
The sketch is tasteful, your authored material stylish.
nonetheless, you command get bought an shakiness over
that you wish be delivering the following. unwell unquestionably come
more formerly again since exactly the same nearly a lot often inside case
you shield this increase.
Hi, the whole thing is going well here and ofcourse every one is sharing information, that’s actually excellent, keep up writing.
This article is actually a fastidious one it assists
new the web viewers, who are wishing for blogging.
Thanks for sharing your thoughts. I really appreciate your efforts and
I am waiting for your further post thanks once again.
Hello there, I discovered your blog by the use of Google at the same time as searching for a
similar subject, your website came up, it
looks good. I have bookmarked it in my google bookmarks.
Hi there, simply turned into alert to your blog
through Google, and located that it is really informative.
I’m going to watch out for brussels. I will be grateful if you happen to proceed
this in future. Numerous people shall be benefited from your writing.
Cheers!
Thanx for the effort, keep up the good work Great work, I am going to start a small Blog Engine course work using your site I hope you enjoy blogging with the popular BlogEngine.net.Thethoughts you express are really awesome. Hope you will right some more posts.
Hey there are using WordPress for your site platform? I’m
new to the blog world but I’m trying to get
started and set up my own. Do you require any coding knowledge to
make your own blog? Any help would be really appreciated!
I’m no longer positive where you are getting
your information, but good topic. I needs to spend some time learning more or figuring out more.
Thanks for great info I used to be looking for this information for
my mission.
Way cool! Some extremely valid points! I appreciate you
writing this post plus the rest of the site is also very good.
Hi everybody, here every person is sharing such familiarity, thus it’s fastidious to
read this blog, and I used to visit this website daily.
all the time i used to read smaller articles or reviews that as
well clear their motive, and that is also happening
with this piece of writing which I am reading now.
Hi there, all is going well here and ofcourse every one is sharing
information, that’s really excellent, keep up writing.
Hello there, I do think your blog may be having browser compatibility issues.
When I look at your web site in Safari, it looks fine however, when opening in IE,
it’s got some overlapping issues. I merely wanted to give you a quick heads up!
Other than that, excellent blog!
I like the valuable info you provide in your articles.
I’ll bookmark your weblog and check again here regularly.
I am quite certain I will learn many new stuff right here!
Good luck for the next!
I used to be able to find good advice from your
blog articles.
whoah this blog is magnificent i love reading your posts. Keep up the good work! You know, many people are looking around for this info, you could aid them greatly.