【日常小测】魔术卡

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/20170614-statement.pdf

题目大意

给你$m(m \le 10^3)$种,第$i$种有$a_i$张,共$n(n = \sum\limits_{i = 1}^{m}{a_i} \le 5000)$张卡
现在把所有卡片排成一排,定义相邻两个卡片颜色相同为一个魔术对
询问恰好有$k$个魔术对的本质不同的排列方式有多少种,对$998244353$取模
定义本质不同为:至少有一位上的颜色不同

解题报告

一看就需要套一个广义容斥原理
于是问题变为求“至少有$x$个魔术对的方案数”

于是我们可以钦定第$i$种卡片组成了$j$个魔术对
然后用一个$O(n^2)$的$DP$来求出至少有$x$个魔术对的方案数

为了方便去重,我们先假设相同颜色的卡片有编号,最后再依次用阶乘除掉
考试的时候就是这里没有处理好,想的是钦定的时候直接去重,但这样块与块之间的重复就搞不了,于是$GG$了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5009;
const int MOD = 998244353;

int n, m, K, a[N], pw[N], inv[N], f[N][N], C[N][N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('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;
}

int main() {
	freopen("magic.in", "r", stdin);
	freopen("magic.out", "w", stdout);
	m = read(); n = read(); K = read();
	for (int i = 1; i <= m; i++) {
		a[i] = read();
	}
	C[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= n; j++) {
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
		}
	}
	pw[0] = inv[0] = 1;
	for (int i = 1; i <= n; i++) {
		pw[i] = (LL)pw[i - 1] * i % MOD;
		inv[i] = Pow(pw[i], MOD - 2);
	}
	f[0][0] = 1;
	for (int i = 1, pre_sum = 0; i <= m; i++) {
		pre_sum += a[i] - 1;
		for (int j = 0; j <= pre_sum; j++) {
			for (int k = min(a[i] - 1, j); ~k; k--) {
				f[i][j] = (f[i][j] + (LL)f[i - 1][j - k] * C[a[i]][k] % MOD * pw[a[i] - 1] % MOD * inv[a[i] - 1 - k]) % MOD;
			}
		} 
	}
	int ans = 0;
	for (int i = K, ff = 1; i < n; i++, ff *= -1) {
		f[m][i] = (LL)f[m][i] * pw[n - i] % MOD;
		ans = (ans + (LL)ff * C[i][K] * f[m][i]) % MOD;
	}
	for (int i = 1; i <= m; i++) {
		ans = (LL)ans * inv[a[i]] % MOD;
	}
	printf("%d\n", (ans + MOD) % MOD);
	return 0;
}

214 thoughts to “【日常小测】魔术卡”

  1. Hi there! This is kind of off topic but I need some
    guidance from an established blog. Is it very difficult to set up your own blog?
    I’m not very techincal but I can figure things out pretty quick.
    I’m thinking about creating my own but I’m not sure where to begin. Do you have any
    points or suggestions? Many thanks

  2. That is very fascinating, You’re an overly professional blogger.
    I’ve joined your feed and look forward to in the hunt for
    extra of your fantastic post. Also, I have shared your web site in my social networks

  3. Have you ever thought about including a little bit more than just your articles?

    I mean, what you say is fundamental and everything.
    However imagine if you added some great graphics or videos to give your posts more, “pop”!
    Your content is excellent but with images and video clips, this site could definitely be one
    of the greatest in its field. Awesome blog!

  4. I feel this is one of the such a lot important info for
    me. And i’m satisfied studying your article. But should
    remark on few common things, The site style is great, the articles is really great : D.

    Good activity, cheers

  5. Hello, Neat post. There is a problem along with your
    site in internet explorer, may test this? IE still is the marketplace chief
    and a big portion of other folks will leave out your great writing because of this problem.

  6. It’s appropriate time to make a few plans for the long run and it is
    time to be happy. I’ve learn this put up and
    if I may just I desire to recommend you few fascinating issues or tips.
    Maybe you can write subsequent articles relating to this article.
    I wish to learn even more things approximately it!

  7. Hello there, just became aware of your blog through Google, and found that it’s truly informative.
    I’m gonna watch out for brussels. I will be grateful
    if you continue this in future. A lot of people will be benefited from your writing.
    Cheers!

  8. Hi there this is somewhat of off topic but I was wanting to know if blogs use WYSIWYG editors or if you have to manually code with HTML.
    I’m starting a blog soon but have no coding expertise so I wanted to get guidance from
    someone with experience. Any help would be enormously appreciated!

  9. Hi, i feel that i noticed you visited my website so i came to return the choose?.I am attempting to find things to improve my website!I assume
    its adequate to make use of a few of your concepts!!
    natalielise plenty of fish

  10. When I originally commented I appear to have clicked the -Notify me when new comments are added- checkbox and
    now each time a comment is added I receive 4 emails with the exact same comment.
    There has to be an easy method you are able to remove me from that service?

    Thanks a lot!

  11. Write more, thats all I have to say. Literally, it seems as though you
    relied on the video to make your point. You obviously know what youre talking about,
    why throw away your intelligence on just posting videos to your
    site when you could be giving us something enlightening to read?

  12. Hi there, You’ve done a great job. I will certainly digg it and personally recommend
    to my friends. I’m confident they will be benefited from this website.

  13. A person necessarily assist to make significantly posts I might state.

    That is the first time I frequented your website page and to
    this point? I amazed with the research you made
    to create this actual post extraordinary. Magnificent task!

  14. First off I would like to say terrific blog!
    I had a quick question which I’d like to ask if you do not mind.
    I was curious to find out how you center yourself and clear
    your thoughts before writing. I’ve had a hard time clearing my thoughts in getting my thoughts out.
    I do take pleasure in writing however it just seems like the first 10 to 15
    minutes tend to be wasted simply just trying to figure out how to begin. Any suggestions or hints?
    Many thanks!

  15. You can definitely see your expertise in the article you write.
    The world hopes for even more passionate writers such as you who aren’t afraid to say how they believe.

    At all times go after your heart.

  16. Hi there! I just wanted to ask if you ever have any issues with hackers?
    My last blog (wordpress) was hacked and I ended up losing several weeks of hard
    work due to no data backup. Do you have any solutions to stop
    hackers?

  17. Thank you for the auspicious writeup. It in truth used
    to be a entertainment account it. Look complex to more added
    agreeable from you! By the way, how could we keep up a correspondence?

  18. Hello There. I found your blog using msn.
    This is a very well written article. I will be sure to bookmark it and return to read more of your
    useful information. Thanks for the post. I’ll definitely comeback.

  19. Unquestionably consider that that you stated.
    Your favourite reason appeared to be at the internet the simplest factor to keep in mind of.
    I say to you, I definitely get irked whilst other people think
    about issues that they plainly don’t realize about.
    You controlled to hit the nail upon the highest as neatly as outlined out the whole thing with no need side effect , folks could take a signal.

    Will probably be again to get more. Thanks

  20. Hello there I am so thrilled I found your weblog, I really found you by error, while I was searching
    on Yahoo for something else, Regardless I
    am here now and would just like to say thank you for a incredible post and a all round entertaining blog (I also love the theme/design),
    I don’t have time to read through it all at the minute but I have bookmarked 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 great work.

  21. We are a group of volunteers and opening a new scheme in our community.
    Your web site provided us with valuable info to work on. You’ve done
    a formidable job and our whole community will be grateful to you.

  22. Excellent blog right here! Also your website lots up very fast!
    What host are you the use of? Can I am getting your affiliate hyperlink on your host?
    I desire my site loaded up as fast as yours lol

  23. Hi there this is kind of of off topic but I was wanting to know 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 advice from someone
    with experience. Any help would be greatly appreciated!

  24. Greate pieces. Keep writing such kind of info on your blog.
    Im really impressed by your blog.
    Hello there, You’ve done a fantastic job. I will certainly digg it and individually recommend to my friends.

    I am sure they will be benefited from this web site.

  25. Hiya, I am really glad I’ve found this info. Nowadays bloggers publish only about gossip and net stuff and this is actually annoying. A good blog with interesting content, this is what I need. Thank you for making this web site, and I will be visiting again. Do you do newsletters by email?

  26. you are truly a excellent webmaster. The website loading pace is amazing. It kind of feels that you’re doing any distinctive trick. In addition, The contents are masterpiece. you have performed a wonderful job on this subject!

  27. Heya i’m for the first time here. I found this board and I find It really useful & it helped me out a lot.

    I hope to give something back and help others such as you
    helped me.

  28. I’m amazed, I have to admit. Seldom do I encounter a
    blog that’s both educative and interesting, and without a doubt, you’ve hit
    the nail on the head. The issue is something which too few folks are speaking intelligently about.
    Now i’m very happy that I came across this in my search for
    something relating to this.

  29. Oh my goodness! Amazing article dude! Many thanks, However I am having
    problems with your RSS. I don’t understand the
    reason why I am unable to subscribe to it. Is there anybody
    having similar RSS problems? Anybody who knows the solution will you kindly respond?
    Thanx!!

  30. Undeniably believe that which you said. Your favorite justification seemed to be on the net
    the easiest factor to take into account of.

    I say to you, I definitely get annoyed while other people
    consider issues that they plainly do not know about.

    You managed to hit the nail upon the highest as well as defined out the entire thing without having side effect , people can take a signal.
    Will likely be back to get more. Thanks

  31. I think the admin of this site is genuinely working hard in favor of his
    website, for the reason that here every stuff is
    quality based information.

  32. Its such as you learn my thoughts! You seem to know a lot about this, like you
    wrote the ebook in it or something. I think that you just could
    do with a few % to force the message house a bit, however instead of that, this
    is wonderful blog. An excellent read. I’ll definitely be back.

  33. Hello, i think that i saw you visited my website so i came to
    “return the favor”.I am attempting to find things to
    improve my website!I suppose its ok to use a
    few of your ideas!!

  34. Spot on with this write-up, I honestly think
    this amazing site needs far more attention. I’ll probably be back again to read through more, thanks for the information!

  35. Please let me know if you’re looking for a author for your weblog.
    You have some really great articles and I think I would be a good asset.

    If you ever want to take some of the load off,
    I’d absolutely love to write some content for your blog
    in exchange for a link back to mine. Please send me an e-mail if interested.
    Thanks!

  36. Simply want to say your article is as surprising. The clarity in your post is just nice and i could assume you’re an expert on this subject. Fine with your permission let me to grab your RSS feed to keep updated with forthcoming post. Thanks a million and please continue the gratifying work.

  37. I simply couldn’t leave your web site prior to suggesting that I really loved the standard information an individual provide to your guests?
    Is going to be again frequently to check up on new posts

  38. It is the best 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 suggestions.
    Perhaps you can write next articles referring to this
    article. I wish to read more things about it!

  39. At this time it sounds like Expression Engine is the best blogging platform out there right
    now. (from what I’ve read) Is that what you’re using on your blog?

  40. It is perfect time to make some plans for the long run and it’s time to be happy. I have read this put up and if I could I wish to counsel you few attention-grabbing issues or suggestions. Maybe you can write next articles relating to this article. I desire to read even more things about it!

Leave a Reply

Your email address will not be published. Required fields are marked *