相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4347
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5006924.html
神犇题解Ⅱ:http://blog.csdn.net/lych_cys/article/details/50788730
解题报告
这题暴力$DP$的复杂度是$O(nd \cdot \max \{a_i\})$的,显然不能通过此题
但我们注意到,对于一个数$a_i$来讲,小于等于它的数的NIM和不会超过$2 \cdot a_i$
于是我们将$a_i$排序之后再$DP$,每一次枚举异或值只枚举到$2 \cdot a_i$
又因为$\sum\limits_{i=1}^n{a_i} \le 10^7$ 所以公共的更新次数不会超过$2 \cdot 10^7$
于是总时间复杂度就是$O(md)$的了
虽然$md$可以到$10^8$,而且感觉这个上界非常紧的样子
给人一种严重的跑不过的感觉
但却跑得飞快? 可能是数据比较水吧?
哦,对了,这题还卡内存
连滚动数组都给卡掉了
于是我们学习Claris的技巧,$f[k][j]$和$f[k \ xor \ a_i][j]$一起更新就可以啦!
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int M = 500009; const int N = 1100000; const int MOD = 1000000007; int n,D,XOR,f[N][10],g[2][10],arr[M]; 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; } int main() { n = read(); D = read(); for (int i=1;i<=n;i++) XOR ^= (arr[i] = read()); sort(arr+1, arr+1+n); f[0][0] = 1; for (int i=1,LIM=1;i<=n;i++) { while (LIM <= arr[i]) LIM <<= 1; for (int v=1,nv;v<LIM;v++) { if ((nv=(arr[i]^v)) <= v) { for (int d=0,t=1%D;d<D;++d,(++t)%=D) { g[1][t] = (f[nv][t] + f[v][d]) % MOD; g[0][t] = (f[nv][d] + f[v][t]) % MOD; } for (int d=0;d<D;d++) { f[nv][d] = g[1][d]; f[v][d] = g[0][d]; } } } } if (n % D == 0) f[XOR][0]--; printf("%d\n",(f[XOR][0]+MOD)%MOD); return 0; }
you’re actually a excellent webmaster. The web site loading pace is amazing. It sort of feels that you’re doing any unique trick. Furthermore, The contents are masterwork. you’ve performed a wonderful task in this topic!
Its like you read my mind! You appear to know a lot about this, like you wrote the book in it or something. I think that you can do with some pics to drive the message home a little bit, but other than that, this is wonderful blog. An excellent read. I will definitely be back.
571759 987653Hi there very cool site!!Guy .. Beautiful .. Wonderful. 8582
385756 957069I enjoy your writing style genuinely enjoying this web internet site . 784269
723879 503857Hey! Do you know if they make any plugins to protect against hackers? Im kinda paranoid about losing everything Ive worked hard on. Any recommendations? 120643
947183 309215Just wanna input on few common items, The site style is perfect, the articles is quite great : D. 346706
583380 490061You completed several great points there. I did specific searches on the problem and discovered numerous folks go in conjunction with along with your blog. 915736
186108 971432An incredibly intriguing examine, I may possibly possibly not concur entirely, but you do make some really valid points. 455353
238274 627328Hey there! Someone in my Myspace group shared this internet site with us so I came to take a look. Im surely enjoying the details. Im bookmarking and will be tweeting this to my followers! Exceptional weblog and outstanding style and design. 954682
676201 26684excellent issues altogether, you simply gained a new reader. What could you recommend about your post that you made some days in the past? Any positive? 869353
332207 724437some truly intriguing information , properly written and broadly speaking user genial . 826476
924085 921082Vi ringrazio, considero che quello che ho letto sia ottimo 579266
509811 491094building websites is not only enjoyable, but it can also generate an income for yourself;; 332455
236800 792346You completed various great points there. I did a search on the theme and identified the majority of folks will consent with your weblog. 20761
602133 38287This really is a excellent blog. Keep up all the work. I too enjoy to weblog. This really is great everyone sharing opinions 427783
132878 2273101 can undertake all sorts of advised excursions with assorted limousine functions. Various offer wonderful courses and numerous can take clients for just about any ride your bike more than the investment banking area, or even for a vacation to new york. ??????? 958132