相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4589
解题报告
我们考虑用SG函数来暴力DP
显然可以用FWT来优化多项式快速幂
总的时间复杂度:$O(n \log n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int MOD = 1000000007; const int REV = 500000004; bool vis[N]; int arr[N]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline int Pow(int w, int t) { int ret = 1; for (; t; t >>= 1, w = (LL)w * w % MOD) { if (t & 1) { ret = (LL)ret * w % MOD; } } return ret; } inline void FWT(int *a, int len, int opt = 1) { for (int d = 1; d < len; d <<= 1) { for (int i = 0; i < len; i += d << 1) { for (int j = 0; j < d; j++) { int t1 = a[i + j], t2 = a[i + j + d]; if (opt == 1) { a[i + j] = (t1 + t2) % MOD; a[i + j + d] = (t1 - t2) % MOD; } else { a[i + j] = (LL)(t1 + t2) * REV % MOD; a[i + j + d] = (LL)(t1 - t2) * REV % MOD; } } } } } int main() { for (int n, m; ~scanf("%d %d", &n, &m); ) { memset(arr, 0, sizeof(arr)); for (int i = 2; i <= m; i++) { if (!vis[i]) { arr[i] = 1; for (int j = i << 1; 0 <= j && j <= m; j += i) { vis[j] = 1; } } } int len = 1; for (; len <= m; len <<= 1); FWT(arr, len); for (int i = 0; i < len; i++) { arr[i] = Pow(arr[i], n); } FWT(arr, len, -1); printf("%d\n", (arr[0] + MOD) % MOD); } return 0; }
You actually make it seem so easy with your presentation but
I find this matter to be actually something which I
think I would never understand. It seems too complicated and extremely broad for me.
I am looking forward for your next post, I’ll try to
get the hang of it!
Oh my goodness! Incredible article dude!
Thank you so much, However I am encountering issues with your RSS.
I don’t know the reason why I cannot subscribe to
it. Is there anybody getting similar RSS issues? Anyone who knows the solution will you kindly respond?
Thanx!!
I have read so many articles or reviews about
the blogger lovers however this article is actually a nice post, keep it up.
Hey! Do you know if they make any plugins to assist with Search
Engine Optimization? I’m trying to get my blog to rank
for some targeted keywords but I’m not seeing very good success.
If you know of any please share. Thank you!
Hi there to every one, as I am actually eager of reading this webpage’s post to be updated regularly.
It carries fastidious material.
This post will help the internet viewers for creating new web site or even a blog from start to end.
I do agree with all the ideas you have introduced for your post.
They are really convincing and will definitely work.
Still, the posts are too brief for starters. May you please extend them a bit from next time?
Thanks for the post.
Wonderful, what a web site it is! This weblog gives useful data to us, keep it up.
I every time used to read paragraph in news papers but now as I am a user of internet so from now I
am using net for posts, thanks to web.
Wow that was strange. I just wrote an really long comment
but after I clicked submit my comment didn’t show up.
Grrrr… well I’m not writing all that over again.
Anyways, just wanted to say fantastic blog!
Admiring the dedication you put into your website and in depth information you provide.
It’s great to come across a blog every once in a while that isn’t the same old rehashed material.
Great read! I’ve bookmarked your site and I’m including your RSS
feeds to my Google account.
I always spent my half an hour to read this weblog’s articles or reviews everyday along
with a mug of coffee.
Hi there, just became alert to your blog through Google, and found that it is really informative.
I am gonna watch out for brussels. I will be
grateful if you continue this in future. Numerous people
will be benefited from your writing. Cheers!
You are so awesome! I don’t believe I have read through a single thing like
that before. So good to find another person with a
few genuine thoughts on this subject. Seriously..
many thanks for starting this up. This web site is something that is
needed on the web, someone with some originality!
Greetings! Very helpful advice in this particular article! It is the little changes that make the biggest changes.
Thanks a lot for sharing!
No matter if some one searches for his necessary thing, so he/she
desires to be available that in detail, thus that thing is maintained over here.
Hey there! I know this is sort of off-topic however I had
to ask. Does building a well-established blog such as yours require a lot of work?
I am brand new to writing a blog however I do write
in my journal everyday. I’d like to start a blog so I can share
my personal experience and feelings online. Please let me know if you have any kind of suggestions or tips for new aspiring blog
owners. Thankyou!
I don’t even know how I ended up right here, but I thought this post was good.
I do not realize who you’re however certainly you are going to a well-known blogger in case you are
not already. Cheers!
Hey there! I could have sworn I’ve been to this website before but
after checking through some of the post I realized it’s new to me.
Anyhow, I’m definitely delighted I found it and I’ll be bookmarking and checking back often!
I got this website from my buddy who informed me on the topic of this web page and now this time I am
browsing this web site and reading very informative
articles at this place.
Hello! I could have sworn I’ve been to this website
before but after going through many of the posts I realized it’s new to
me. Anyways, I’m certainly pleased I found it and I’ll be
bookmarking it and checking back frequently!
What’s up to every single one, it’s genuinely a nice for me to
go to see this web page, it consists of priceless Information.
What i don’t understood is in truth how you’re now not really
a lot more smartly-favored than you may be now. You are so intelligent.
You already know therefore significantly when it comes to
this topic, made me for my part consider it from a lot of varied angles.
Its like women and men aren’t fascinated unless it’s one thing to do with Girl gaga!
Your individual stuffs outstanding. At all times handle it
up!
What’s up to all, because I am in fact eager of reading this website’s post
to be updated daily. It carries pleasant material.
Pretty nice post. I just stumbled upon your weblog and wanted to say that I’ve
really enjoyed surfing around your blog posts.
In any case I’ll be subscribing to your rss feed and I hope you write again very soon!
Nice weblog right here! Additionally your web site so much up very fast!
What web host are you the use of? Can I get your affiliate link for your host?
I wish my website loaded up as quickly as yours lol
I really like what you guys are up too. This kind of clever work and coverage!
Keep up the awesome works guys I’ve incorporated you guys to my
blogroll.
Hmm it appears like your site ate my first comment (it was super long)
so I guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog.
I too am an aspiring blog blogger but I’m still new to everything.
Do you have any helpful hints for newbie blog writers?
I’d genuinely appreciate it.
Pretty component of content. I simply stumbled upon your site and in accession capital to say that I get actually enjoyed account your blog posts.
Any way I’ll be subscribing to your augment or even I achievement you get admission to constantly fast.
Hi, nice work. I really appeaciate the information you are providing through your website, i have alwasy find it helpful. Keep up the awsome work.
Hello, i read your blog from time to time and i own a similar one and i was just wondering if you get a lot of spam feedback?
If so how do you reduce it, any plugin or anything you can advise?
I get so much lately it’s driving me mad so any support is very much appreciated.
I’m not that much of a internet reader to be honest but your sites really
nice, keep it up! I’ll go ahead and bookmark your website
to come back later. All the best
Hi there! I know this is kind of off topic but I was
wondering if you knew where I could find a captcha plugin for my
comment form? I’m using the same blog platform as yours and I’m
having trouble finding one? Thanks a lot! pof natalielise
Heya i’m for the first time here. I came
across this board and I to find It really helpful & it helped me out much.
I hope to provide something back and help others like you aided me.
hello there and thank you for your information – I have
definitely picked up anything new from right here. I did however expertise several technical issues using this web site, since I experienced to
reload the web site a lot of times previous to I could get it to load
correctly. I had been wondering if your web host is
OK? Not that I’m complaining, but sluggish loading instances times will very frequently affect your
placement in google and can damage your quality score if ads and marketing
with Adwords. Anyway I am adding this RSS to my e-mail and
could look out for much more of your respective intriguing content.
Ensure that you update this again very soon.
Simply wish to say your article is as amazing. The clarity in your post is just cool and i can assume you are an expert on this subject.
Fine with your permission allow me to grab your feed to keep up to date with forthcoming
post. Thanks a million and please continue the gratifying work.
I like the valuable information you supply to your articles.
I will bookmark your blog and test again here regularly.
I am reasonably certain I’ll be informed a lot of new stuff proper right here!
Best of luck for the following!
I relish, cause I found just what I was looking for.
You have ended my four day lengthy hunt! God Bless you man. Have a nice day.
Bye
Your style is unique in comparison to other folks
I’ve read stuff from. I appreciate you for posting when you’ve got
the opportunity, Guess I will just bookmark this site.
Great beat ! I would like to apprentice while you amend
your website, how could i subscribe for a blog web site?
The account helped me a acceptable deal. I had been a little bit acquainted of this your broadcast offered bright
clear idea
I have to thank you for the efforts you have put in penning this website. I’m hoping to view the same high-grade content by you later on as well. In fact, your creative writing abilities has encouraged me to get my own blog now 😉
Every weekend i used to pay a visit this site,
for the reason that i wish for enjoyment, as this this web page conations truly pleasant funny material too.
Hi there just wanted to give you a quick heads up and let you know a few of the images aren’t loading correctly.
I’m not sure why but I think its a linking issue. I’ve tried
it in two different internet browsers and both show the
same outcome.
Hey I am so grateful I found your weblog, I really found
you by error, while I was browsing on Bing for something
else, Anyways I am here now and would just like to say
thank you for a fantastic post and a all round interesting blog (I also love the theme/design), I don’t have time to read it all at the minute but
I have book-marked it and also included your RSS feeds, so when I have time I will be back to read a great deal more, Please
do keep up the fantastic work.
Hi there to every body, it’s my first go to see of this blog; this website consists
of amazing and genuinely fine information in favor
of readers.
This info is worth everyone’s attention. When can I find out more?
Link exchange is nothing else however it is just placing the other person’s weblog link on your page at appropriate place and other person will also do similar in favor of you.
This is very interesting, You’re a very skilled blogger.
I have joined your feed and look forward to seeking more of your excellent post.
Also, I’ve shared your site in my social networks!
Wonderful article! We are linking to this great content on our website.
Keep up the good writing.
Wow that was unusual. I just wrote an extremely long comment but after I clicked submit my comment didn’t
show up. Grrrr… well I’m not writing all that over again. Regardless, just wanted to say superb blog!
I am genuinely thankful to the owner of this web site who has shared this impressive article at here.
Fantastic beat ! I wish to apprentice while you amend your website, how can i
subscribe for a blog site? The account helped me a acceptable deal.
I had been a little bit acquainted of this your broadcast provided bright clear idea
Hey there! Do you use Twitter? I’d like to follow you if
that would be ok. I’m undoubtedly enjoying your blog and look forward to new posts.
Amazing things here. I am very satisfied to see your post.
Thanks a lot and I’m having a look ahead to contact you.
Will you please drop me a e-mail?
Good day! Do you use Twitter? I’d like to follow you if that would
be okay. I’m definitely enjoying your blog and look forward to new posts.
I was more than happy to uncover this great site.
I wanted to thank you for your time due to this fantastic
read!! I definitely really liked every part of it and
i also have you bookmarked to check out new information in your web site.
Hi colleagues, how is all, and what you would like to say about this paragraph,
in my view its truly remarkable for me.
This blog was… how do I say it? Relevant!! Finally I have found something that helped me.
Kudos!
Amazing! Its truly awesome piece of writing, I have got
much clear idea on the topic of from this article.
It’s fantastic that you are getting thoughts from this paragraph as well as from our dialogue made at this time.
Pretty! This was a really wonderful post. Thank you for your provided information.
I was curious if you ever considered changing the structure of your blog?
Its very well written; I love what youve got to
say. But maybe you could a little more in the way of content
so people could connect with it better. Youve got an awful lot of text for only having 1 or 2 images.
Maybe you could space it out better?
The very heart of your writing whilst appearing agreeable in the beginning, did not really work well with me after some time. Somewhere throughout the paragraphs you actually managed to make me a believer unfortunately just for a while. I however have got a problem with your jumps in assumptions and you might do nicely to help fill in all those gaps. In the event that you actually can accomplish that, I will undoubtedly be amazed.
I’m gone to say to my little brother, that he should also pay
a quick visit this website on regular basis to obtain updated from most recent gossip.
Hi! I simply would like to offer you a big thumbs up for your excellent
information you have got here on this post. I am coming back to your blog for more soon.
Hi, after reading this amazing paragraph i am as well delighted to share my knowledge here with colleagues.
I was suggested this website by means of my cousin. I am not certain whether this
post is written through him as nobody else recognize such particular
approximately my difficulty. You are amazing! Thank you!
Hi there all, here every one is sharing these familiarity,
thus it’s pleasant to read this weblog, and I used to visit this blog everyday.
Good day very cool blog!! Guy .. Excellent ..
Superb .. I will bookmark your website and take the feeds additionally?
I am glad to find numerous helpful info right here within the put up,
we need develop extra techniques on this regard, thank you for sharing.
. . . . .
What i don’t understood is in truth how you are now not really much more
smartly-liked than you may be right now. You’re so intelligent.
You realize thus considerably in relation to this topic, made me in my view imagine
it from so many numerous angles. Its like women and men are
not involved except it’s one thing to do with Girl gaga! Your individual
stuffs nice. All the time maintain it up!
Thanks for sharing your thoughts on quest bars cheap. Regards
Hi there just wanted to give you a quick heads up
and let you know a few of the pictures aren’t loading correctly.
I’m not sure why but I think its a linking issue. I’ve tried it in two different browsers
and both show the same results.
Excellent weblog here! Also your web site lots up fast! What web host
are you using? Can I am getting your associate link to your host?
I desire my website loaded up as quickly as yours lol
Thank you for another great article. Where else could anyone get that kind of information in such a perfect approach of writing?
I’ve a presentation subsequent week, and I am at the
look for such information.
Hi, i feel that i saw you visited my site thus i got here to
go back the desire?.I am trying to to find
issues to improve my site!I suppose its adequate to
use a few of your concepts!!
Hi, its good post about media print, we all be familiar
with media is a wonderful source of facts.
It’s actually a cool and useful piece of information. I am satisfied that you shared this useful
information with us. Please stay us informed like this.
Thank you for sharing.
Your means of telling all in this article is really good, every one be capable of easily understand it,
Thanks a lot.
Hello There. I found your weblog using msn. That is a really well written article.
I will make sure to bookmark it and return to read extra
of your helpful info. Thanks for the post. I’ll certainly return.
We’re a group of volunteers and starting a new scheme in our community.
Your website offered us with valuable information to
work on. You’ve done a formidable job and
our entire community will be grateful to you.
I’m not that much of a internet reader to be honest but your blogs really nice, keep it
up! I’ll go ahead and bookmark your website to come back down the road.
Cheers
It is actually a great and useful piece of info.
I’m glad that you shared this helpful information with us.
Please stay us informed like this. Thanks for sharing.
I was extremely pleased to discover this website. I want
to to thank you for your time for this particularly
wonderful read!! I definitely loved every little bit
of it and i also have you book-marked to look at new information on your site.
I blog often and I truly thank you for your content.
Your article has truly peaked my interest. I am going to book mark your blog and keep checking
for new information about once per week. I opted in for your RSS feed as
well.
I think this is one of the so much vital info for me.
And i’m glad reading your article. However wanna observation on some common issues, The website style is perfect, the articles is actually
nice : D. Just right task, cheers
You actually make it seem so easy along with your presentation but I in finding this matter to be really one thing which I feel I’d never understand. It sort of feels too complicated and extremely vast for me. I am taking a look forward in your next put up, I will attempt to get the hold of it!
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 will right away take hold of your rss as I can not to find your email subscription link or
newsletter service. Do you’ve any? Kindly allow me realize so that I may just subscribe.
Thanks.
Hello there, I found your blog by the use of Google at the same time as searching
for a comparable subject, your site came up, it appears great.
I’ve bookmarked it in my google bookmarks.
Hi there, simply changed into aware of your blog
thru Google, and located that it’s really informative.
I’m gonna be careful for brussels. I will appreciate if you proceed this in future.
A lot of other folks might be benefited out of your
writing. Cheers!
Yes! Finally someone writes about sling tv.
I must thank you for the efforts you have put in penning this
website. I am hoping to view the same high-grade content from you
later on as well. In fact, your creative writing abilities has
inspired me to get my very own site now 😉
I’ve been absent for some time, but now I remember why I used to love this blog. Thank you, I will try and check back more frequently. How frequently you update your site?
I needed to thank you for this wonderful read!!
I absolutely loved every little bit of it. I have you saved
as a favorite to check out new stuff you post…
It’s fantastic that you are getting ideas from this
article as well as from our argument made here.
A round of applause for your article post.Much thanks again. Awesome.
Thanks-a-mundo for the blog post. Keep writing.