相关链接
题目传送门:http://codeforces.com/contest/814/problem/E
官方题解:http://codeforces.com/blog/entry/52449
神犇题解Ⅰ:https://loj.ac/article/37
神犇题解Ⅱ:http://kczno1.blog.uoj.ac/blog/2660
解题报告
我们考虑分层图的话
那每一层的一个点一定会与上一层的某个点相连,剩下的度数只能层内消化
又因为这题对祖先有严格的限制,所以每一层都是原序列中连续的一段
于是$O(n^5)$的暴力$DP$就可以写了
至于$O(n^3)$的$DP$,就是$DP$套$DP$
预处理出转移的$buf$,然后转移的时候直接乘就好了
但这个预处理的时候要讨论很多情况啊,反正我自己考场上是想不出来的_(:з」∠)_
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 52; const int MOD = 1000000007; const int REV2 = 500000004; int n, f[N][N], s2[N], s3[N], buf[N][N][N], C[N][N], prm[N]; inline int read() { char c=getchar(); int f=1,ret=0; 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(); f[read() + 1][1] = 1; for (int i = 2; i <= n; i++) { s2[i] = s2[i - 1]; s3[i] = s3[i - 1]; if (read() == 2) { s2[i]++; } else { s3[i]++; } } C[0][0] = 1; for (int i = 1; i <= n; i++) { C[i][0] = 1; for (int j = 1; j <= i; j++) { C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD; } } prm[2] = 1; for (int i = 3; i <= n; i++) { prm[i] = REV2; for (int j = 2; j < i; j++) { prm[i] = (LL)prm[i] * j % MOD; } } for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { for (int k = 0; k <= n; k++) { if (i == 0 && j == 0 && k == 0) { buf[i][j][k] = 1; } else if (i == 0 && j == 0) { for (int l = 2; l < k; l++) { (buf[i][j][k] += ((LL)buf[i][j][k - 1 - l] * C[k - 1][l] % MOD) * prm[l + 1] % MOD) %= MOD; } } else if (i == 0) { buf[i][j][k] = j > 1? (LL)(j - 1) * buf[i][j - 2][k] % MOD: 0; (buf[i][j][k] += k? (LL)k * buf[i][j][k - 1] % MOD: 0) %= MOD; } else { buf[i][j][k] = j? (LL)j * buf[i - 1][j - 1][k] % MOD: 0; (buf[i][j][k] += k? (LL)k * buf[i - 1][j + 1][k - 1] % MOD: 0) % MOD; } } } } for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (f[i][j]) { int t2 = s2[i] - s2[j]; int t3 = s3[i] - s3[j]; for (int k = i + 1; k <= n; k++) { f[k][i] = (f[k][i] + (LL)f[i][j] * buf[k - i][t2][t3]) % MOD; } } } } int ans = 0; for (int i = 1; i <= n; i++) { ans = (ans + (LL)f[n][i] * buf[0][s2[n] - s2[i]][s3[n] - s3[i]]) % MOD; } cout<<ans<<endl; return 0; }
Good day! I know this is kinda off topic but I was wondering which blog platform are you using for this website?
I’m getting sick and tired of WordPress because I’ve had
problems with hackers and I’m looking at alternatives
for another platform. I would be awesome if you could point
me in the direction of a good platform.
Great post however , I was wanting to know if you could write a litte more on this topic?
I’d be very thankful if you could elaborate a little bit further.
Many thanks!
Hello it’s me, I am also visiting this web site daily, this site is genuinely nice
and the viewers are actually sharing good thoughts.
Excellent, what a weblog it is! This webpage presents helpful data
to us, keep it up.
I every time emailed this web site post page to all my contacts, since if like to read
it then my links will too.
I think this is among the most significant info for me. And i’m glad reading your
article. But wanna remark on few general
things, The web site style is wonderful, the articles is really great
: D. Good job, cheers
whoah this weblog is fantastic i like reading your articles.
Stay up the great work! You recognize, a lot of people are looking round
for this info, you can aid them greatly.
Does your website have a contact page? I’m
having a tough time locating it but, I’d like to
send you an e-mail. I’ve got some ideas for your blog you might
be interested in hearing. Either way, great blog and I look forward to seeing it grow over time.
I read this paragraph fully regarding the comparison of
most recent and preceding technologies, it’s amazing article.
It’s truly very complex in this active life to listen news on Television, thus I just use internet
for that purpose, and obtain the latest news.
My partner and I stumbled over here by a different web page and thought I might
check things out. I like what I see so now i am following you.
Look forward to exploring your web page again.
It’s perfect time to make some plans for the
future and it is time to be happy. I have read this post and if I could I wish to suggest you some interesting
things or tips. Maybe you can write next articles referring to this
article. I desire to read even more things about it!
Do you mind if I quote a few of your posts as long as
I provide credit and sources back to your weblog? My blog is in the very
same area of interest as yours and my users would definitely benefit
from some of the information you provide here. Please let me know
if this alright with you. Thanks!
Hi I am so thrilled I found your blog, I really found
you by error, while I was browsing on Google for something
else, Anyhow I am here now and would just like to say thanks a lot for a marvelous post and a all round
exciting blog (I also love the theme/design), I don’t have time to read it all at the minute but I
have bookmarked it and also added in your RSS feeds, so when I have time I will be back to read more, Please do keep up the awesome job.
I am not sure where you are getting your
info, but great topic. I needs to spend some time learning much
more or understanding more. Thanks for wonderful information I was looking for this information for my mission.
Excellent post. Keep posting such kind of information on your site.
Im really impressed by it.
Hi there, You have done an excellent job. I will certainly
digg it and personally recommend to my friends. I am sure
they will be benefited from this site.
Wow, this piece of writing is nice, my younger sister is analyzing
these things, thus I am going to convey her.
Hello, all is going sound here and ofcourse every one is sharing facts, that’s truly fine, keep up writing.
If you are going for best contents like myself, simply pay a visit this site all the
time for the reason that it presents feature contents, thanks
Hey There. I found your blog using msn. This is a really well written article.
I will be sure to bookmark it and return to read more of your useful
info. Thanks for the post. I will definitely return.
Hello, the whole thing is going nicely here and ofcourse every one is sharing information, that’s genuinely fine,
keep up writing.
This piece of writing is truly a nice one it helps new
internet viewers, who are wishing for blogging. natalielise pof
Thanks for one’s marvelous posting! I seriously enjoyed reading it, you can be a great author.
I will be sure to bookmark your blog and will
often come back down the road. I want to encourage you to definitely continue your great writing, have a nice evening!
hello there and thank you for your information – I have certainly picked up
anything new from right here. I did however expertise some technical points using this website, as I experienced to
reload the site 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 could damage your quality score if ads and marketing with Adwords.
Well I am adding this RSS to my e-mail and could look out for much more of your respective interesting
content. Make sure you update this again very soon.
Hey! This is kind of off topic but I need some guidance from an established blog.
Is it hard to set up your own blog? I’m not very techincal but
I can figure things out pretty fast. I’m thinking about setting up
my own but I’m not sure where to begin. Do
you have any ideas or suggestions? With thanks
Awesome blog! Is your theme custom made or did you download it from somewhere?
A theme like yours with a few simple adjustements
would really make my blog jump out. Please let me know where you got your theme.
Thanks a lot natalielise pof
I am actually grateful to the owner of this site who has shared this wonderful article at at this time.
You really make it seem really easy together with your presentation however
I in finding this matter to be really one thing which I believe I’d by
no means understand. It sort of feels too complex and very extensive for me.
I’m having a look ahead for your next publish, I will attempt
to get the grasp of it!
Wow, superb blog layout! How long have you been blogging for?
you made blogging look easy. The overall look
of your site is wonderful, let alone the content!
Wow, that’s what I was searching for, what a information! present here
at this weblog, thanks admin of this site. pof natalielise
Wow, incredible blog layout! How long have you been blogging
for? you make blogging look easy. The overall look of
your web site is wonderful, as well as the content!
Hi there! This is my first comment here so I just wanted to give a quick shout out and tell you I really enjoy reading your articles. Can you recommend any other blogs/websites/forums that deal with the same subjects? Thanks a lot!
Hello! I could have sworn I’ve visited this website before but after looking at
some of the posts I realized it’s new to me. Anyhow, I’m definitely happy I found
it and I’ll be bookmarking it and checking back regularly!
natalielise pof
I absolutely love your website.. Great colors & theme. Did you build this website yourself? Please reply back as I’m attempting to create my own personal website and want to know where you got this from or exactly what the theme is named. Thanks!
What i don’t understood is in fact how you are now not really a lot more smartly-appreciated than you might be now. You’re so intelligent. You realize therefore significantly in terms of this topic, produced me in my view consider it from so many various angles. Its like women and men are not interested until it is something to do with Lady gaga! Your personal stuffs excellent. All the time maintain it up!
Hello this is kinda of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually code with HTML. I’m starting a blog soon but have no coding experience so I wanted to get advice from someone with experience. Any help would be enormously appreciated!
When I initially commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is added I get four e-mails with the same comment. Is there any way you can remove people from that service? Thanks!
This post provides clear idea for the new visitors of blogging, that actually how to do running a blog.
For newest information you have to visit the web and on internet I found this website as a most excellent web page for newest updates.
I blog quite often and I truly thank you for
your information. This great article has really peaked my interest.
I will take a note of your site and keep checking for new
details about once a week. I subscribed to your RSS feed as well.
Your mode of explaining all in this post is actually nice, all be able to simply know it, Thanks a lot.
Way cool! Some extremely valid points! I appreciate you
writing this write-up plus the rest of the website is extremely good.
Hey! I understand this is kind of off-topic but I needed to ask.
Does running a well-established website such as yours take a lot of work?
I am completely new to blogging however I do write in my journal daily.
I’d like to start a blog so I can easily share my own experience and feelings online.
Please let me know if you have any recommendations or tips for brand new aspiring blog owners.
Appreciate it!
Hi there to all, it’s really a good for me to go to
see this web site, it contains priceless Information.
It’s remarkable to pay a quick visit this website and
reading the views of all colleagues concerning this piece of
writing, while I am also keen of getting know-how.
I know this web page gives quality depending articles or
reviews and extra stuff, is there any other web page which gives these kinds of information in quality?
I am truly glad to glance at this website posts which
carries tons of helpful facts, thanks for providing these statistics.
My coder is trying to persuade me to move to .net
from PHP. I have always disliked the idea because of
the expenses. But he’s tryiong none the less. I’ve been using Movable-type on various websites for about a year and am
anxious about switching to another platform.
I have heard excellent things about blogengine.net.
Is there a way I can transfer all my wordpress posts into it?
Any help would be greatly appreciated!
Everything is very open with a really clear explanation of
the issues. It was really informative. Your website is extremely
helpful. Many thanks for sharing!
Hello, Neat post. There is a problem along with your site in web explorer, could check this?
IE nonetheless is the marketplace chief and a big part of folks will omit your excellent writing due to
this problem.
Hi to all, how is everything, I think every one is getting more from
this web page, and your views are fastidious in favor of new viewers.
Heya are using WordPress for your site platform? I’m new to the blog world but I’m trying to get started and create
my own. Do you need any coding expertise to make your own blog?
Any help would be really appreciated!
Wow, that’s what I was looking for, what a data! present here at this blog,
thanks admin of this website.
Love Diagrams and all about them !
Best state in UK !!
I love your blog.. very nice colors & theme. Did you create this website yourself or did you hire someone to do it for you?
Plz answer back as I’m looking to design my own blog and would like to
know where u got this from. appreciate it
This article is genuinely a fastidious one it helps new web visitors,
who are wishing in favor of blogging.
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.
Wow that was strange. I just wrote an really long comment but after
I clicked submit my comment didn’t appear. Grrrr…
well I’m not writing all that over again. Anyhow,
just wanted to say excellent blog!
Hi, just wanted to say, I liked this blog
post. It was practical. Keep on posting!
What a stuff of un-ambiguity and preserveness of
valuable experience on the topic of unexpected feelings.
Hi there, just wanted to tell you, I enjoyed this blog post.
It was inspiring. Keep on posting!
I do not even understand how I stopped up right here, but
I believed this submit used to be good. I don’t recognise who you’re
but definitely you’re going to a famous blogger in the event you aren’t already.
Cheers!
At this time I am ready to do my breakfast, after having my breakfast coming
again to read more news.
I could not refrain from commenting. Very well written!
Hello There. I found your weblog the use of msn. This is
an extremely neatly written article. I’ll make sure
to bookmark it and return to read extra of your useful information. Thank you for the post.
I’ll certainly comeback.
Wonderful beat ! I wish to apprentice while you amend your web site, how could i
subscribe for a blog site? The account helped me a acceptable deal.
I had been a little bit acquainted of this your broadcast offered bright clear idea
Outstanding story there. What happened after?
Good luck!
If you wish for to obtain much from this post then you have to apply such techniques to your won blog.
Somebody essentially help to make critically posts I’d
state. This is the very first time I frequented your web page and to
this point? I surprised with the research you made to make this particular submit incredible.
Excellent job!
Hey there just wanted to give you a brief
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.
I got this site from my buddy who informed me on the topic of this website and
now this time I am browsing this site and reading very informative
articles or reviews at this time.
I was recommended this web site by my cousin. I am not sure whether this post is written by him as no one else
know such detailed about my trouble. You are wonderful!
Thanks!
Just want to say your article is as amazing. The clarity to your submit is simply
cool and that i could think you are knowledgeable on this subject.
Fine along with your permission allow me to snatch your RSS feed to keep up to
date with forthcoming post. Thank you 1,000,000 and please keep up the gratifying work.
Howdy this is kind of of off topic but I was wondering if blogs use WYSIWYG editors or
if you have to manually code with HTML. I’m starting a blog soon but have no coding skills so I wanted to get guidance
from someone with experience. Any help would be enormously appreciated!
With havin so much content and articles do you ever run into any issues of plagorism or copyright violation? My website has a lot of completely unique content I’ve either created myself or outsourced but it seems a lot of it is popping it up all over the internet without my authorization. Do you know any ways to help protect against content from being ripped off? I’d certainly appreciate it.
hello!,I like your writing very much! proportion we communicate more approximately your post on AOL?
I need a specialist in this house to resolve my problem.
Maybe that is you! Having a look ahead to see you.
great submit, very informative. I ponder why the opposite specialists of this sector do not realize
this. You must continue your writing. I am sure, you have
a great readers’ base already!
Hey! I know this is kinda off topic but I was wondering if you knew where I could locate 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!
Hey There. I found your weblog using msn. This is a really neatly written article.
I will make sure to bookmark it and return to learn extra of your
helpful info. Thanks for the post. I will certainly comeback.
Thank you so much! If you want to see me naked click my name!
A motivating discussion is worth comment. I believe that you ought to write more on this subject matter, it might not be a taboo subject but generally people do not speak about such topics. To the next! Best wishes!!
Hi, I believe your website could be having browser compatibility problems.
When I take a look at your site in Safari, it looks fine
however, if opening in I.E., it’s got some overlapping issues.
I just wanted to provide you with a quick heads up! Other than that, wonderful website!
We stumbled over here by a different page and thought I may
as well check things out. I like what I see so now i’m following you.
Look forward to looking at your web page again.
That is a good tip particularly to those fresh to the blogosphere.
Brief but very precise information… Thanks for sharing this one.
A must read article!
It’s difficult to find knowledgeable people about this
subject, but you sound like you know what you’re talking about!
Thanks
I was recommended this blog by my cousin. I’m not sure whether this post is written by him as no one else know such detailed about my problem.
You are incredible! Thanks!
I couldn?t resist commenting. Well written!|
worth enough for me. In my opinion,
Great info, thanks for sharing it!
Thanks for your hard work!
thanks for the helpful info!
Great post. I used to be checking constantly this weblog and I’m inspired!
Extremely helpful info specifically the remaining part :
) I maintain such info much. I used to be seeking this particular info
for a long time. Thank you and best of luck.
May I simply say what a relief to find somebody who really understands what they are discussing on the internet.
You definitely understand how to bring a problem to light and make it important.
More and more people have to look at this and understand this
side of your story. I can’t believe you are not more popular
because you certainly possess the gift.
Great blog thank you
Hello there! I know this is kinda 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 difficulty finding one? Thanks a lot!
Great info, thanks for sharing it!
A big thank you for your blog post.Much thanks again. Want more.