相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4735
神犇题解:http://blog.csdn.net/neither_nor/article/details/64919143
吐槽
我只会$O(mn2^n)$的暴力$DP$
然而正解长成这样,为什么$n$给这么小?
给人一种这题有妙妙的做法的错觉……
解题报告
我们把正常的牌看成$-1$的话,那么实际上就是要让每一个地方的前缀和$\ge 1$
现在考虑在末尾加上一个$-1$,那么是不是就是处末尾以外的地方$\ge 1$,而末尾的前缀和为$0$?
现在考虑把这$m+1$个元素拿出来做一个环排列
仔细观察可以发现:一种环排列能且仅能对应一种合法摆放
于是我们求出环排列的个数就可以了,最后再去一下多加的那个$-1$的影响
最终答案:$\frac{m!}{m-n+1}$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int MOD = 998244353; 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() { int n = read(), m = 0, ans = 1; for (int i=1;i<=n;i++) m += read(); for (int i=2;i<=m;i++) ans = ((LL)ans * ((i!=m-n+1)?i :1)) % MOD; cout<<ans; return 0; }
This design is incredible! You certainly know how to keep a reader
amused. Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Wonderful job.
I really enjoyed what you had to say, and more than that, how you presented
it. Too cool!
I’ll immediately take hold of your rss as I can not in finding your e-mail subscription hyperlink or newsletter service.
Do you have any? Please permit me recognise in order that I may just subscribe.
Thanks.
Hi my friend! I want to say that this post is amazing, great
written and come with almost all significant infos.
I’d like to look extra posts like this .
Whats up very nice site!! Guy .. Excellent .. Amazing ..
I’ll bookmark your blog and take the feeds additionally?
I’m glad to seek out a lot of useful info here within the
post, we’d like develop more techniques on this regard, thanks for sharing.
. . . . .
Please let me know if you’re looking for a writer for your
blog. You have some really great posts and I believe I would
be a good asset. If you ever want to take some of the load off, I’d absolutely love
to write some articles for your blog in exchange
for a link back to mine. Please shoot me an e-mail if
interested. Thank you!
Can you tell us more about this? I’d want to find out more details.
After I originally left a comment I seem to have clicked the
-Notify me when new comments are added- checkbox and from now on whenever a comment is added I recieve 4 emails with the exact same comment.
Is there a way you are able to remove me from that service?
Many thanks!
Hmm is anyone else encountering problems with the
pictures on this blog loading? I’m trying to determine
if its a problem on my end or if it’s the blog. Any suggestions would be greatly
appreciated.
Hi, i think that i saw you visited my blog so i came to “return the favor”.I am trying to find things to enhance my website!I suppose
its ok to use a few of your ideas!!
Greetings! I know this is somewhat 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 difficulty
finding one? Thanks a lot!
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.
you have a great blog here! would you like to make some invite posts on my blog?
I really like what you guys tend to be up too. This sort of clever work and coverage!
Keep up the terrific works guys I’ve you
guys to my personal blogroll.
I really like reading through a post that can make men and women think.
Also, many thanks for allowing for me to comment!
Hi there very nice web site!! Guy .. Beautiful ..
Amazing .. I’ll bookmark your site and take the feeds also?
I am happy to seek out a lot of useful information here
within the publish, we want develop more strategies on this regard, thanks for sharing.
. . . . .
Your way of describing everything in this article is truly
good, all be able to simply know it, Thanks a lot.
Hello everyone, it’s my first go to see at this web page, and piece of writing is truly fruitful in favor of me, keep up posting these types
of articles.
Good post. I learn something new and challenging on sites
I stumbleupon every day. It will always be helpful to read content from other writers and use
a little something from other web sites.
wonderful points altogether, you just won a emblem new reader.
What might you suggest in regards to your publish that you just made a few days ago?
Any sure?
Greetings, I think your blog may be having internet browser compatibility problems.
Whenever I look at your website in Safari, it
looks fine however, when opening in I.E., it’s got some overlapping issues.
I merely wanted to give you a quick heads up! Other than that, great blog!
WOW just what I was searching for. Came here by searching for sling tv
I take pleasure in, lead to I found just what I used to be taking
a look for. You’ve ended my 4 day lengthy hunt!
God Bless you man. Have a great day. Bye
Magnificent beat ! I would like to apprentice while you amend your web site,
how could i subscribe for a blog site? The account aided me a acceptable deal.
I had been a little bit acquainted of this your broadcast offered bright clear concept
Very good information. Lucky me I recently found your
website by accident (stumbleupon). I have bookmarked
it for later!
Hi there! I could have sworn I’ve been to this blog before but after reading through some of the post I realized it’s new to me. Anyhow, I’m definitely glad I found it and I’ll be book-marking and checking back often!