相关链接
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4349
神犇题解：http://blog.csdn.net/u013486414/article/details/48130553
题目大意
求${n \choose i},i \in [1,n]$中有多少个奇数
其中$n \le 10^{18}$
解题报告
原题相当于求${n \choose i} \% 2$有多少个为$1$
考虑使用$Lucas$定理，将模数设为$2$
此时相当于把$n,i$都转成了二进制下，然后单独考虑每一位
因为${1 \choose 1} = {1 \choose 0} = {0 \choose 0} = 1,{0 \choose 1} = 0$
所以当$n$的那个二进制位为$1$的时候，$i$那一位可以为$0/1$，但当$n$那一位为$0$时，$i$只能为$0$
所以最终方案数为$2^{\sum\limits_{i=0}^{63}{(n>>i) \& 1}}$
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main() {
for (LL n,ans;~scanf("%I64d",&n);){
ans = pow(2, __builtin_popcountll(n)) + 0.5;
cout<<ans<<endl;
}
return 0;
}
Hi! Would you mind if I share your blog with my myspace
group? There’s a lot of folks that I think would really enjoy your content.
Please let me know. Thank you
Hey I know this is off topic but I was wondering if you knew of any widgets I could
add to my blog that automatically tweet my newest twitter
updates. I’ve been looking for a plug-in like this for quite
some time and was hoping maybe you would have some experience with something like this.
Please let me know if you run into anything.
I truly enjoy reading your blog and I look forward to your new updates.
I have been browsing online more than 3 hours today, yet I never found any interesting article like yours.
It is pretty worth enough for me. In my view,
if all site owners and bloggers made good content as you did, the net will be a lot more
useful than ever before.
Good information. Lucky me I came across your blog by accident (stumbleupon).
I have book-marked it for later!
I’ll right away seize your rss as I can not find your e-mail subscription link or newsletter service.
Do you have any? Please let me recognise in order that I may subscribe.
Thanks.
I don’t even understand how I stopped up right here, but I assumed this publish was once
great. I do not know who you are but definitely you are going to a famous blogger if you happen to
aren’t already. Cheers!
Spot on with this write-up, I seriously feel this
amazing site needs a lot more attention. I’ll probably be back again to read through more, thanks for the info!
I am not sure where you’re getting your info, but great topic.
I needs to spend some time learning more or understanding
more. Thanks for fantastic information I was looking for this info for
my mission.
Hello There. I found your blog using msn. This is an extremely well written article.
I will be sure to bookmark it and come back to read more of your useful information. Thanks for the post.
I will certainly comeback.
Hey there! Someone in my Facebook group shared this website with us so I came
to check it out. I’m definitely loving the information.
I’m book-marking and will be tweeting this to my followers!
Exceptional blog and superb style and design.
hello!,I really like your writing so a lot! proportion we be in contact more approximately your article on AOL? I require an expert in this house to solve my problem. Maybe that’s you! Taking a look ahead to see you.
I visited multiple web sites except the audio quality for audio
songs present at this web site is really marvelous.
I all the time used to read post in news
papers but now as I am a user of internet so from now
I am using net for posts, thanks to web.
Yes! Finally someone writes about sling tv.
I do not even know how I ended up here, but I
thought this post was great. I don’t know who you are but certainly you are going to a famous blogger if you aren’t
already 😉 Cheers!
I could not resist commenting. Very well written!
Hello all, here every one is sharing such experience,
thus it’s good to read this website, and I used to pay a quick visit this website everyday.
Please let me know if you’re looking for a author for your blog.
You have some really great posts and I think I would
be a good asset. If you ever want to take some of the load off, I’d love to write some
content for your blog in exchange for a link back to mine.
Please shoot me an e-mail if interested. Kudos!
Your style is so unique compared to other people I have read stuff from.
I appreciate you for posting when you’ve got the opportunity, Guess I will just book mark
this site.
Howdy! I could have sworn I’ve been to your blog before but after browsing through
some of the posts I realized it’s new to me. Nonetheless,
I’m certainly pleased I came across it and I’ll be book-marking it and checking back often!
Greetings! Very helpful advice on this article! It is the little changes that make the biggest changes. Thanks a lot for sharing!