相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4197
解题报告
考虑把小于$\sqrt{n}$的因数状压起来
然后将所有数按照大于$\sqrt{n}$的因数分组
最后分组$DP$即可
总时间复杂度:$O(500 \cdot 3^8)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 509; const int M = 6561; int pri[] = {2, 3, 5, 7, 11, 13, 17, 19}; int n, gpri[N], spri[N], sta1[M], sta2[M], tt[M][N][3]; LL MOD, *f, *g, *h, arr1[M], arr2[M], arr3[M], ori[M]; vector<int> sta[N]; inline void relax(LL &a, LL b) { a = (a + b) % MOD; } inline int num(int x, int t) { for (; t; x /= 3, t--); return x % 3; } inline int SET(int w, int t, int v) { static int buf[] = {1, 3, 9, 27, 81, 243, 729, 2187}; int ret = 0; for (int i = 0; i < 8; i++, w /= 3, t >>= 1) { if (t & 1) { ret += buf[i] * v; } else { ret += buf[i] * (w % 3); } } return ret; } int main() { freopen("dinner.in", "r", stdin); freopen("dinner.out", "w", stdout); cin>>n>>MOD; for (int i = 0; i < M; i++) { for (int j = 0; j < 8; j++) { int t = num(i, j); if (t == 1) { sta1[i] |= 1 << j; } else if (t == 2) { sta2[i] |= 1 << j; } } } for (int i = 0; i < M; i++) { for (int j = 0; j < (1 << 8); j++) { for (int k = 1; k <= 2; k++) { tt[i][j][k] = SET(i, j, k); } } } for (int i = 2; i <= n; i++) { gpri[i] = i; for (int j = 0; j < 8; j++) { if (gpri[i] % pri[j] == 0) { spri[i] |= (1 << j); while (gpri[i] % pri[j] == 0) { gpri[i] /= pri[j]; } } } } f = arr1, g = arr2, h = arr3; g[0] = f[0] = 1; for (int i = 2; i <= n; i++) { if (gpri[i] == 1) { for (int j = M - 1; ~j; j--) { if (g[j]) { int sta = 0; for (int k = 0; k < 8; k++) { if (spri[i] >> k & 1) { sta |= num(j, k); } } if (sta == 0) { relax(f[tt[j][spri[i]][1]], g[j]); relax(f[tt[j][spri[i]][2]], g[j]); } else if (sta < 3) { relax(f[tt[j][spri[i]][sta]], g[j]); } } } memcpy(g, f, sizeof(arr1)); swap(f, g); } else { sta[gpri[i]].push_back(spri[i]); } } for (int i = 2; i <= n; i++) { if (!sta[i].empty()) { memcpy(h, g, sizeof(arr1)); memcpy(ori, g, sizeof(arr1)); for (int j = 0; j < (int)sta[i].size(); j++) { int vv = sta[i][j]; for (int k = M - 1; ~k; k--) { if (g[k]) { int s1 = vv & sta1[k]; if (!s1) { relax(f[tt[k][vv][2]], g[k]); } } } memcpy(g, f, sizeof(arr1)); swap(f, g); } memcpy(f, h, sizeof(arr1)); for (int j = 0; j < (int)sta[i].size(); j++) { int vv = sta[i][j]; for (int k = M - 1; ~k; k--) { if (h[k]) { int s2 = vv & sta2[k]; if (!s2) { relax(f[tt[k][vv][1]], h[k]); } } } memcpy(h, f, sizeof(arr1)); swap(f, h); } for (int k = 0; k < M; k++) { f[k] = g[k] = (f[k] + g[k] - ori[k]) % MOD + MOD; } } } LL ans = 0; for (int i = 0; i < M; i++) { relax(ans, f[i]); } printf("%lld\n", ans); return 0; }
The other day, while I was at work, my cousin stole my iphone and tested
to see if it can survive a thirty foot drop, just so she can be
a youtube sensation. My iPad is now broken and she has 83 views.
I know this is completely off topic but I had to share it with
someone!
I blog quite often and I really thank you for your information.
This great article has truly peaked my interest.
I’m going to take a note of your website and keep checking for new information about once per week.
I opted in for your Feed as well.
What’s up mates, its fantastic paragraph on the topic of
teachingand completely defined, keep it up all the time.
It’s going to be finish of mine day, except before finish I am reading this fantastic paragraph to increase my knowledge.
magnificent submit, very informative. I’m wondering why the other
specialists of this sector don’t realize this. You must proceed your writing.
I’m sure, you’ve a huge readers’ base already!
Hi there everybody, here every person is sharing such knowledge, so it’s fastidious to read this webpage, and I used to pay
a visit this blog every day.
Hello there, I discovered your website via Google whilst
looking for a related topic, your web site got
here up, it looks good. I have bookmarked it in my google bookmarks.
Hi there, just changed into alert to your blog via
Google, and found that it’s truly informative.
I am going to be careful for brussels. I’ll be grateful if you continue this in future.
Numerous other people will likely be benefited from your writing.
Cheers!
I really love your site.. Excellent colors & theme.
Did you build this website yourself? Please reply back as I’m planning to create my own site and would love to find out where you got this from or exactly what the theme is named.
Thank you!
I think this is among the most significant info for me.
And i am glad reading your article. But want to remark on few general things, The web site style is perfect,
the articles is really great : D. Good job, cheers
Your way of telling the whole thing in this piece of writing
is genuinely fastidious, all can easily be aware of it,
Thanks a lot.
constantly i used to read smaller articles
or reviews which as well clear their motive, and that is
also happening with this article which I am reading at this time.
hey there and thank you for your info – I have definitely picked up something new from right
here. I did however expertise a few technical points using this
website, since I experienced to reload the web site a lot
of times previous to I could get it to load properly.
I had been wondering if your hosting is OK? Not that I am complaining, but sluggish loading instances times will
often affect your placement in google and can damage your high
quality score if advertising and marketing with Adwords.
Well I’m adding this RSS to my e-mail and could look out for a
lot more of your respective intriguing content. Ensure
that you update this again very soon.
This piece of writing is truly a pleasant one it helps new internet users, who are wishing
in favor of blogging.
I have been browsing online more than three hours today, yet I never found any
interesting article like yours. It is pretty worth enough for me.
In my view, if all web owners and bloggers made good content
as you did, the net will be much more useful than ever before.
Excellent post. Keep posting such kind of info on your page.
Im really impressed by your site.
Hello there, You’ve performed an incredible job.
I’ll definitely digg it and individually suggest
to my friends. I’m sure they’ll be benefited from this site.
Pretty great post. I just stumbled upon your weblog and wished to mention that
I have truly enjoyed browsing your blog posts. After all I will
be subscribing for your rss feed and I am hoping you write again soon!
Hey there! I understand this is sort of off-topic
however I had to ask. Does building a well-established blog like yours take a massive amount work?
I’m brand new to running a blog however I do write in my
diary every day. I’d like to start a blog so I can share my own experience and thoughts online.
Please let me know if you have any ideas or tips for new
aspiring bloggers. Appreciate it! natalielise plenty of fish
Amazing issues here. I am very satisfied to peer your article.
Thanks a lot and I am having a look forward to touch you. Will you kindly drop me a mail?
I really like what you guys are usually up too. This type of clever work and
exposure! Keep up the wonderful works guys I’ve incorporated you guys to our blogroll.
I am truly delighted to read this weblog posts which consists of
lots of helpful information, thanks for providing these data.
natalielise pof
Can you tell us more about this? I’d love to find out some additional information.
I’m gone to inform my little brother, that he should also pay a
visit this blog on regular basis to obtain updated from latest reports.
Greetings from Carolina! I’m bored to tears at work so I decided to browse your site on my iphone during lunch break.
I love the info you present here and can’t wait to take a look when I get home.
I’m amazed at how quick your blog loaded on my mobile ..
I’m not even using WIFI, just 3G .. Anyhow, great site!
Hey there I am so thrilled I found your web site, I really found you by accident, while I was looking on Google
for something else, Nonetheless I am here now and would
just like to say thanks for a tremendous post and a
all round exciting blog (I also love the theme/design), I don’t have
time to browse it all at the minute but I have book-marked
it and also added your RSS feeds, so when I have time
I will be back to read much more, Please do keep up the excellent work.
Great website. Plenty of helpful information here. I am sending it to several buddies ans also sharing in delicious.
And of course, thanks on your sweat! natalielise plenty of fish
Superb blog! Do you have any recommendations for aspiring writers?
I’m planning to start my own site soon but I’m a little lost on everything.
Would you recommend starting with a free platform
like WordPress or go for a paid option? There are so many choices out there that I’m
completely confused .. Any tips? Thanks a lot!
An intriguing discussion is definitely worth comment. I do
believe that you ought to write more about this subject, it might not be a taboo subject but usually people do not talk about these topics.
To the next! Cheers!!
You can certainly see your expertise in the work you write.
The arena hopes for more passionate writers like you who aren’t afraid
to say how they believe. At all times follow your heart.
I am truly pleased to read this webpage posts which contains plenty of useful data, thanks for providing these
kinds of statistics.
whoah this weblog is wonderful i really like
studying your articles. Keep up the good work! You recognize, lots of persons are
looking round for this info, you can aid them greatly.
Great beat ! I would like to apprentice while you amend your site, how could i
subscribe for a blog website? The account aided me a acceptable deal.
I had been a little bit acquainted of this your broadcast provided bright clear concept
You actually make it appear so easy with your presentation however I find this matter to
be actually something that I feel I might never understand.
It sort of feels too complicated and extremely huge for me.
I am taking a look forward to your subsequent post, I will
try to get the hold of it!
Oh my goodness! Amazing article dude! Many thanks, However I am going through
difficulties with your RSS. I don’t know why I am unable to join it.
Is there anybody having identical RSS problems? Anyone who
knows the answer can you kindly respond? Thanks!!
Hello to every one, the contents present at this web site are
truly awesome for people knowledge, well, keep up the nice work fellows.
I am sure this article has touched all the internet people, its really really fastidious post on building up new blog.
I’m not sure where you’re getting your info, but good topic.
I needs to spend some time learning more or understanding more.
Thanks for magnificent info I was looking for this info for my mission.
This is my first time go to see at here and i am actually impressed to read everthing at one place.
My partner and I stumbled over here by a different web page and thought I should check things out.
I like what I see so now i am following you.
Look forward to going over your web page for a second time.
Hi! Someone in my Myspace group shared this site with us so I came to check
it out. I’m definitely loving the information. I’m bookmarking and will be tweeting this
to my followers! Wonderful blog and wonderful style and design.
My spouse and I stumbled over here from a different web address and thought I might as
well check things out. I like what I see so now i’m following
you. Look forward to exploring your web page yet again.
I think the admin of this site is truly working hard for his web site, for the reason that here every stuff is quality based stuff.
Valuable information. Fortunate me I found your web site unintentionally, and I am shocked why this twist of fate did not took place earlier!
I bookmarked it.
It’s a pity you don’t have a donate button! I’d
definitely donate to this fantastic blog! I suppose for now i’ll settle for book-marking and adding your RSS
feed to my Google account. I look forward to brand new updates and will talk about this blog
with my Facebook group. Chat soon!
Hello, i think that i saw you visited my weblog thus i came to “return the favor”.I’m attempting to find things to improve my web site!I suppose its ok to use
a few of your ideas!!
I’m gone to say to my little brother, that he should
also visit this website on regular basis to obtain updated from newest gossip.
With havin so much content do you ever run into any problems
of plagorism or copyright violation? My site has a lot
of unique content I’ve either written myself or outsourced but
it looks like a lot of it is popping it up all over the internet without my
permission. Do you know any solutions to help reduce content from
being ripped off? I’d genuinely appreciate it.
Hi there very cool site!! Guy .. Beautiful .. Superb .. I’ll bookmark your site
and take the feeds additionally? I am happy to seek
out numerous useful information right here within the post, we want work out more strategies in this regard, thank you for sharing.
. . . . .
hey there and thank you for your info – I’ve definitely picked
up anything new from right here. I did however expertise some technical issues using this website, since I experienced to reload the
website a lot of times previous to I could get it to load correctly.
I had been wondering if your web hosting is OK? Not that I am
complaining, but sluggish loading instances times will sometimes affect your placement in google and can damage your high-quality score if advertising and
marketing with Adwords. Anyway I am adding this
RSS to my e-mail and could look out for much more of your
respective exciting content. Make sure you update this
again soon.
Hello there! Would you mind if I share your blog with my twitter group?
There’s a lot of folks that I think would really appreciate your
content. Please let me know. Many thanks
Everything is very open with a very clear description of the issues.
It was really informative. Your site is very helpful. Thanks for
sharing!
you are actually a good webmaster. The web site loading pace is incredible.
It seems that you’re doing any distinctive trick.
Moreover, The contents are masterpiece. you have performed
a magnificent process on this subject!
It’s impressive that you are getting thoughts from this article as well as from our discussion made at
this place.
hello!,I love your writing so much! proportion we be
in contact extra approximately your post on AOL? I need a specialist in this space to solve my problem.
May be that is you! Looking forward to peer
you.
Your mode of describing everything in this article is actually fastidious, every one be able to without
difficulty understand it, Thanks a lot.
Why visitors still use to read news papers when in this technological
globe the whole thing is presented on net?
For the reason that the admin of this website is working, no question very shortly it will be renowned, due to its feature contents.
Excellent article. Keep posting such kind of info on your site.
Im really impressed by your blog.
Hey there, You have performed an incredible job. I will certainly digg it and for
my part suggest to my friends. I’m sure they will be benefited from this web site.
My brother recommended I might like this website. He was totally right.
This post actually made my day. You cann’t imagine
just how much time I had spent for this information! Thanks!
I always spent my half an hour to read this weblog’s articles or reviews all the time along with a cup of coffee.
Awesome article.
That is really attention-grabbing, You are an excessively professional blogger.
I have joined your rss feed and look ahead to seeking extra of your magnificent post.
Additionally, I have shared your site in my social networks
What’s up, its nice article concerning media print, we all know media is a enormous
source of facts.
My brother suggested I might like this website. He was entirely
right. This post truly made my day. You can not imagine simply how much time I had spent for this information! Thanks!
It’s nearly impossible to find knowledgeable people for
this topic, however, you seem like you know what you’re talking about!
Thanks
Nice post. I used to be checking constantly this blog and I am
impressed! Extremely useful information specifically the remaining part :
) I take care of such info much. I used to be seeking this certain information for a long time.
Thank you and good luck.
I used to be suggested this web site by way of my cousin. I’m no
longer positive whether this put up is written via him
as nobody else realize such unique approximately my difficulty.
You’re amazing! Thank you!
If some one desires expert view regarding running a blog after that i advise
him/her to visit this website, Keep up the good
job.
Nice blog here! Also your site loads up very fast! What web host are you using?
Can I get your affiliate link to your host? I wish my web site
loaded up as fast as yours lol
This excellent website truly has all the info I needed concerning this
subject and didn’t know who to ask.
Greetings! Very useful advice in this particular post!
It is the little changes which will make the biggest changes.
Many thanks for sharing!
Ahaa, its nice discussion on the topic of this post
at this place at this blog, I have read all that, so now me also commenting here.
I’m really loving the theme/design of your web site. Do you ever run into any browser compatibility problems?
A small number of my blog readers have complained about my site not operating correctly in Explorer
but looks great in Safari. Do you have any ideas to help
fix this issue?
I am really loving the theme/design of your website. Do you ever run into any browser compatibility issues?
A small number of my blog readers have complained about my website not working
correctly in Explorer but looks great in Chrome.
Do you have any ideas to help fix this problem?
If you desire to obtain a great deal from this paragraph
then you have to apply these strategies to your won webpage.
This post provides clear idea in support of the new viewers of blogging,
that actually how to do blogging.
What’s up, yeah this piece of writing is really pleasant and
I have learned lot of things from it about blogging. thanks.
Great web site you have here.. It’s hard to find high quality writing like yours nowadays.
I truly appreciate people like you! Take care!!
If you desire to take much from this post
then you have to apply such methods to your won blog.
Hi to every , for the reason that I am actually keen of reading this weblog’s post to be updated on a regular basis.
It contains good stuff.
Very energetic article, I loved that a lot. Will there
be a part 2?
Today, while I was at work, my sister stole my iPad and tested to see if
it can survive a forty foot drop, just so she can be a youtube sensation. My
iPad is now broken and she has 83 views. I know this is totally off topic but I had to share it with
someone!
Excellent website. Plenty of useful info here. I am sending it to a few
buddies ans additionally sharing in delicious. And certainly,
thanks to your sweat!
I was suggested this website by means of my cousin. I am now not certain whether this publish is written by way of him as no one else understand such exact approximately my problem. You are incredible! Thanks!
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.
Thanks for one’s marvelous posting! I certainly enjoyed reading it,
you are a great author.I will make sure to bookmark your blog
and will often come back later on. I want to encourage you continue your
great writing, have a nice afternoon!
Hello to all, how is the whole thing, I think
every one is getting more from this web site, and your views are nice
in support of new users.
I seriously love your blog.. Great colors & theme.
Did you develop this website yourself? Please reply back as I’m attempting to create my very own website
and want to learn where you got this from or what the theme is
called. Appreciate it!
Thank you for some other great post. The place else may anyone get that kind of info in such a perfect manner
of writing? I’ve a presentation next week, and I’m at the look for such info.
This is a really good tip especially to those fresh to the blogosphere.
Short but very precise information… Many thanks for sharing
this one. A must read post!
This site was… how do you say it? Relevant!! Finally I’ve found
something which helped me. Appreciate it!
Attractive part of content. I simply stumbled upon your blog and
in accession capital to say that I acquire actually loved
account your weblog posts. Any way I will be subscribing on your feeds or even I achievement you
get entry to consistently quickly.
Hi, I want to subscribe for this weblog to get most up-to-date updates, so where can i
do it please help.
My partner and I stumbled over here by a different web address and thought
I might as well check things out. I like what I see so now i’m following you.
Look forward to looking over your web page repeatedly.
Hi there, I enjoy reading all of your article. I wanted to
write a little comment to support you.
I am continually looking online for ideas that can benefit me. Thank you!
Thanks for sharing, this is a fantastic article post.Thanks Again. Cool.
Looking forward to reading more. Great blog article.Really looking forward to read more. Fantastic.