【Codeforces 814E】An unavoidable detour for home

相关链接

题目传送门: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;
}

98 thoughts to “【Codeforces 814E】An unavoidable detour for home”

  1. 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.

  2. 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

  3. 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.

  4. 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.

  5. 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!

  6. 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!

  7. 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.

  8. 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.

  9. 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.

  10. 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!

  11. 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.

  12. 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

  13. 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

  14. 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!

  15. 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!

  16. 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!

  17. 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!

  18. 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!

  19. 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!

  20. 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!

  21. 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!

  22. 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.

  23. 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!

  24. 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!

  25. 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.

  26. 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

  27. 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.

  28. 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!

  29. 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!

  30. 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.

  31. 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

  32. 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!

  33. 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.

  34. 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.

  35. 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!

  36. 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.

  37. 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!

  38. 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.

  39. 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.

  40. 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.

  41. 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!!

  42. 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!

  43. 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.

  44. 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!

  45. 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!

  46. 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.

  47. 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.

  48. 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!

发表评论

电子邮件地址不会被公开。 必填项已用*标注