相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1442
中文题解：http://www.shuizilong.com/house/archives/poi-xiii-stage-3-problem-crystals/
解题报告
首先我们定义“折越”：
这一位上可以选1，但选了0
如果我们从高位到低位考虑的话，如果有一位发生了折越，那之后的东西就可以随便取了
于是我们考虑在每一种方案第一次发生折越的时候将其统计进入答案
对每个数我们分情况讨论：
- 第i位只能填0
那么剩下的位数的可能情况就有a & (1<<i)种辣- 第i位可以发生折越
那么不发生折越的情况同第一类
发生折越之后，因为可以随便取，所以得乘上1<<i
这样的话，我们类似数位DP一样，从高位到低位依次DP就好
另外，此题没有取模的操作，需要用unsigned long long才能通过本题
Code
#include<bits/stdc++.h>
#define LL unsigned long long
using namespace std;
const int N = 59;
LL n,arr[N],vout;
int main() {
cin>>n;
for (int i=1;i<=n;i++) cin>>arr[i];
for (int t=31;~t;t--) {
LL f[3],t1,t2,od; od = 0;
f[0] = 1; f[1] = f[2] = 0;
for (int i=1,tmp;i<=n;i++) {
tmp = (arr[i] & ((1LL<<t) - 1)) + 1;
if (arr[i] & (1LL<<t)) {
od ^= 1;
t1 = f[0] + (f[2] << t);
t2 = f[1] << t;
f[0] *= tmp;
(f[1] *= tmp) += t1;
(f[2] *= tmp) += t2;
} else {
f[0] *= tmp;
f[1] *= tmp;
f[2] *= tmp;
}
}
if (od) {vout += f[1] - 1; break;}
else vout += f[2];
}
cout<<vout;
return 0;
}
好文章！666，学习了
I conceive other website proprietors should take this internet site as an model, very clean and great user genial style.
Hey there! This is kind of off topic but I need some advice from an established blog. Is it very difficult to set up your own blog? I’m not very techincal but I can figure things out pretty fast. I’m thinking about creating my own but I’m not sure where to start. Do you have any ideas or suggestions? Thank you
290481 942132HURRAY! cant balladeer. by virtue of himself by what name highly. 185416
621028 731792I conceive this web internet site contains some rattling fantastic info for every person : D. 519530
292182 851405I appreciate you taking the time to create this post. It has been really valuable to me surely. Value it. 619499
921053 474042I added this post to my favorites and program to return to digest a lot more soon. It is easy to read and realize as nicely as intelligent. I truly enjoyed my 1st read by way of of this post. 270862
120700 660150Nice write-up. It does shed some light on the concern. By the for those interested in binary options can get an exclusive binary options bonus. 668234
184016 57051I enjoy this internet site, will surely arrive back. Make certain you carry on writing high quality posts. 692205
440013 909218Hi there, just became aware of your blog through Google, and identified that its truly informative. Ill be grateful if you continue this in future. Lots of men and women will benefit from your writing. Cheers! 933585
287367 354639Having read this I thought it was very informative. I appreciate you taking the time and effort to put this write-up together. I once once more find myself spending approach to considerably time both reading and commenting. But so what, it was still worth it! 227535
458255 319611Good one, there is in fact some excellent facts on this post some of my subscribers may locate this useful, will send them a link, several thanks. 68286
683050 848349I like this web website quite much, Its a actually good post to read and get info . 955494