相关链接
题目传送门: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; }
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
I think the admin of this website is actually working hard for his web page, as here every data is quality based
data.
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
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!
Thank you for the good writeup. It in fact was a amusement account it.
Look advanced to more added agreeable from you! However, how can we communicate?
Pretty! This was an extremely wonderful post. Thanks for supplying this information.
This article is actually a fastidious one it helps new web visitors, who are wishing in favor of blogging.
It’s actually a nice and helpful piece of info.
I am happy that you simply shared this helpful info
with us. Please keep us informed like this. Thanks for sharing.
If some one desires expert view on the topic of blogging afterward
i suggest him/her to visit this website, Keep up
the fastidious work.
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
Hello, this weekend is pleasant designed for me, for the reason that this point in time i am reading
this great educational post here at my home.
I enjoy reading a post that will make men and women think.
Also, thanks for permitting me to comment!
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.
My family always say that I am killing my time here at net,
except I know I am getting familiarity every day by reading thes fastidious articles or
reviews.
It is not my first time to pay a visit this website, i am browsing this web site dailly and get nice information from
here all the time.
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!
Thanks a lot for sharing this with all of us you actually
recognize what you are speaking about! Bookmarked. Kindly also consult
with my website =). We will have a link change agreement between us
Hey there, You have done a great job. I will definitely digg it and
personally recommend to my friends. I am confident they’ll be benefited from this
website.
Hi, i think that i noticed you visited my site so i came to return the prefer?.I’m trying to find things to improve my website!I assume its good
enough to make use of a few of your concepts!!
There is certainly a great deal to learn about this issue.
I love all of the points you made.
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!
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!
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
When someone writes an paragraph he/she maintains the image of a user
in his/her brain that how a user can know it. Therefore that’s why this piece of writing is perfect.
Thanks!
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!
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?
Saved as a favorite, I love your website! pof natalielise
I read this piece of writing completely on the topic of the comparison of most up-to-date and earlier technologies,
it’s amazing article.
It’s awesome to go to see this site and reading
the views of all colleagues about this paragraph, while I am also zealous of getting experience.
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.
Good way of describing, and nice article to obtain information on the
topic of my presentation subject, which i am going to deliver in academy.
plenty of fish natalielise
Hello, just wanted to tell you, I loved this blog post.
It was helpful. Keep on posting! natalielise pof
Pretty great post. I simply stumbled upon your blog and wished to say that I’ve really loved browsing your weblog posts.
After all I will be subscribing in your feed and I’m hoping you write again soon!
My brother recommended I might like this website. He was entirely right.
This post actually made my day. You cann’t imagine just how
much time I had spent for this info! Thanks!
Hi to every one, it’s actually a nice for me to pay a visit this
website, it consists of helpful Information.
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!
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!
Paragraph writing is also a excitement, if you be familiar with afterward
you can write if not it is difficult to write.
Thank you for sharing your thoughts. I really appreciate your efforts and I will be waiting for your further write ups thanks once again.
Yes! Finally someone writes about minecraft games.
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.
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?
Hey there! I just wish to give you a huge thumbs up for your excellent information you’ve got
right here on this post. I am coming back to your blog for more soon.
Paragraph writing is also a excitement, if you be acquainted with after that you can write otherwise it is complex to write.
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?
Wow, this paragraph is pleasant, my sister is analyzing these things, thus
I am going to convey her.
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.
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
“Its difficult to find informative and precise information but here I found”
Major thanks for the blog post.Thanks Again. Will read on…
A big thank you for your post.Really thank you! Cool.
This is one awesome blog.Much thanks again. Really Cool.
I am so grateful for your article.Thanks Again. Great.
Thanks-a-mundo for the blog article.Thanks Again. Will read on…
A round of applause for your article post.Really thank you! Really Great.
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.
Really appreciate you sharing this post.Really looking forward to read more. Want more.
I loved your blog. Keep writing.
I loved your article.Really looking forward to read more. Awesome.
Thanks so much for the blog post.Much thanks again. Will read on…
I loved your post.Thanks Again. Keep writing.
Say, you got a nice blog. Will read on…
Really informative article.Thanks Again. Awesome.
Im thankful for the article post.Thanks Again. Cool.
Very good post.Thanks Again. Fantastic.
Major thanks for the blog article.Thanks Again. Much obliged.
I really like and appreciate your blog post. Cool.
This post is in fact a nice one it assists new internet
people, who are wishing for blogging.
Wow, great article.Much thanks again. Awesome.
Thanks again for the blog article.
Appreciate you sharing, great blog.Really looking forward to read more. Will read on…
It’s actually very difficult in this full of activity life to listen news on Television,
so I only use world wide web for that reason, and take the latest news.
I cannot thank you enough for the blog article.Really thank you!
Enjoyed every bit of your blog article.Thanks Again. Great.
Say, you got a nice blog post.Thanks Again. Really Great.
Major thankies for the article post.Really thank you!
This is one awesome article post.Much thanks again. Will read on…
Enjoyed every bit of your article post.Much thanks again.
I value the blog post.Really thank you! Great.
Wow, great article post.Really looking forward to read more. Much obliged.
I think this is a real great blog post.Thanks Again. Really Great.
I value the blog.Really looking forward to read more. Really Great.
wow, awesome article post.Much thanks again. Fantastic.
I really like and appreciate your blog article.Thanks Again. Really Great.
Thank you for your article post.Much thanks again. Cool.
Very good article post.Really looking forward to read more. Really Cool.
I cannot thank you enough for the blog post. Really Great.
Thanks for sharing, this is a fantastic blog post.Really thank you!
Fantastic blog article.
Major thanks for the article.Much thanks again. Awesome.
Say, you got a nice blog.Much thanks again. Great.
Thank you ever so for you blog article. Fantastic.
Really enjoyed this blog article.Really thank you! Cool.
Im grateful for the blog article. Want more.
I truly appreciate this article post. Great.
I loved your post. Really Cool.
A round of applause for your post. Will read on…
Appreciate you sharing, great blog article.Really looking forward to read more. Awesome.
A round of applause for your blog article.Really looking forward to read more. Really Cool.
Thanks-a-mundo for the article.Much thanks again. Want more.
Major thankies for the blog article.Really thank you! Really Cool.
Major thankies for the blog.Really looking forward to read more. Really Cool.
Im grateful for the article post.Really looking forward to read more. Much obliged.
Thank you for your article.Really thank you! Keep writing.
Great blog post.Really looking forward to read more. Will read on…
Thanks a lot for the article post.Really looking forward to read more. Great.
Fantastic post.Much thanks again. Fantastic.
Hey, thanks for the article.Thanks Again. Great.
A round of applause for your article.Thanks Again. Want more.
Im obliged for the blog article.Really thank you! Keep writing.
A big thank you for your post.Really thank you! Cool.
Muchos Gracias for your article.Thanks Again. Cool.
Thanks again for the post. Much obliged.
Major thanks for the blog post.Really looking forward to read more. Will read on…
Hi there colleagues, its wonderful paragraph regarding teachingand fully explained, keep it up all the time.
Thanks so much for the blog.Thanks Again. Great.
wow, awesome blog.Really thank you! Really Cool.
Im grateful for the post.Much thanks again. Cool.
Thanks so much for the blog article. Really Great.
Muchos Gracias for your article.Much thanks again. Will read on…
Thank you for your blog.Thanks Again. Fantastic.
Im grateful for the post.Really thank you! Really Great.
wow, awesome post.Really looking forward to read more. Fantastic.
Thanks for sharing, this is a fantastic article post.Really looking forward to read more. Much obliged.
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.
Hi there! This is my first comment here so I just wanted to give
a quick shout out and say I truly enjoy reading your articles.
Can you suggest any other blogs/websites/forums that go over the same subjects?
Thanks a ton!
Thanks so much for the blog post.Much thanks again. Really Cool.
Thanks so much for the article.
Thanks so much for the article. Cool.
I loved your blog. Fantastic.
Very neat post. Will read on…
Thank you ever so for you article post.Really looking forward to read more. Cool.
Wow, great post.Thanks Again. Awesome.
Thanks again for the blog article.Much thanks again. Cool.
I am so grateful for your article post.Really looking forward to read more. Cool.
Im grateful for the blog post.Much thanks again. Really Cool.
I really like and appreciate your article post.Really thank you! Want more.
A round of applause for your article. Awesome.
I really liked your article.Much thanks again. Really Great.
I really enjoy the post.Really looking forward to read more. Awesome.
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
Thanks so much for the blog post.Really thank you! Fantastic.
Really appreciate you sharing this blog article.Really thank you! Keep writing.
Wow, great article post.Really thank you! Want more.
I am so grateful for your blog article.Really looking forward to read more. Will read on…
I think this is a real great blog post.Really thank you! Great.
Great, thanks for sharing this blog post.Really looking forward to read more. Awesome.
I really liked your blog post.Thanks Again. Fantastic.
Im thankful for the blog.Much thanks again. Cool.
I really like and appreciate your blog article.Much thanks again. Really Great.
Awesome post. Great.
I think this is a real great post.Really thank you! Cool.
Im thankful for the blog article.Much thanks again. Awesome.
Thanks so much for the blog article.Really thank you! Keep writing.
A round of applause for your blog post. Really Great.
Thank you ever so for you blog. Will read on…
Enjoyed every bit of your blog.Really thank you! Really Great.
This is one awesome blog post.Really looking forward to read more. Keep writing.
yahoo got me here. Thanks!
I really like and appreciate your blog article.Really thank you! Great.
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!
Enjoyed every bit of your article.Much thanks again. Great.
Muchos Gracias for your blog post.Thanks Again. Cool.
Wow, great article.Thanks Again. Want more.
Im grateful for the blog post.Really thank you! Much obliged.
This is one awesome post.Really looking forward to read more. Really Great.
Enjoyed every bit of your blog article.Much thanks again. Keep writing.
Thanks again for the blog article.Thanks Again. Great.
Hey, thanks for the article post.Really thank you! Much obliged.
I really like and appreciate your blog.Thanks Again. Will read on…
Thanks-a-mundo for the article. Much obliged.
Thank you ever so for you blog.Much thanks again. Much obliged.
Thank you ever so for you blog.Much thanks again. Much obliged.
Thanks again for the article post.Thanks Again. Really Great.
I really like and appreciate your article.Thanks Again. Fantastic.
Great, thanks for sharing this article. Cool.
A round of applause for your post.Thanks Again. Fantastic.
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.
This is one awesome article.Thanks Again. Awesome.
I’ve got a fresh new list of free proxies. I hope you all can put them to good use.
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?
“Very good article.Thanks Again. Awesome.”
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!
I loved your article post.Much thanks again. Awesome.
You are a very bright person!
That is really attention-grabbing, You’re a very professional
blogger. I have joined your feed and stay up for in search of more
of your fantastic post. Additionally, I have shared your site in my social networks
Very informative article post.Really thank you! Cool.
Very informative blog post.Really looking forward to read more.
Thankfulness to my father who told me on the topic of this website,
this blog is truly amazing.
Thanks-a-mundo for the blog.Thanks Again. Really Cool.
Great article, totally what I was looking for.
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.
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.
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!!
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
Hi to all, the contents present at this web site
are in fact amazing for people experience, well, keep up the nice work fellows.
Really no matter if someone doesn’t know after that its up to other viewers that they
will assist, so here it takes place.
Tremendous things here. I am very satisfied to see your article.
Thanks so much and I am looking forward to touch you.
Will you kindly drop me a mail?
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.
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.
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!!
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!
If you wish for to grow your familiarity just keep visiting this web site and be updated with the
most recent news update posted here.
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!
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.
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
No matter if some one searches for his vital thing,
so he/she wants to be available that in detail,
therefore that thing is maintained over here.
I like the helpful information you provide in your articles.
I will bookmark your blog and check again here regularly.
I am quite certain I’ll learn many new stuff right here!
Good luck for the next!
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!
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?
Hi, the whole thing is going nicely here and ofcourse
every one is sharing data, that’s in fact excellent, keep
up writing.
Aw, this was an exceptionally good post. Spending some time and actual effort to make
a good article… but what can I say… I hesitate a lot
and never seem to get nearly anything done.
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!
Very informative post. Cool.