相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4710
神犇题解：http://www.cnblogs.com/candy99/p/6616858.html
解题报告
先不考虑每个人至少一个的限制条件
那么我们可以将每一类物品分别考虑，用一个插板法就可以解决问题
现在考虑每一个人至少一个的限制
我们可以大力容斥一波！
于是总的时间复杂度就是：$O(nm)$
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2009;
const int MOD = 1000000007;
int n,m,ans,a[N],C[N][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;
}
inline int cal(int x) {
int ret = C[x][n];
for (int i=1;i<=m;i++) {
ret = (LL)ret * C[n-x-1][a[i]+n-x-1] % MOD;
}
return ret;
}
int main() {
n = read(); m = read();
C[0][0] = 1;
for (int i=1;i<N;i++) {
C[0][i] = 1;
for (int j=1;j<N;j++) {
C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
}
}
for (int i=1;i<=m;i++) a[i] = read();
for (int i=0;i<n;i++) {
if (i&1) ans = (ans - cal(i)) % MOD;
else ans = (ans + cal(i)) % MOD;
}
printf("%d\n",(ans+MOD)%MOD);
return 0;
}
Quality content is the important to attract the people to go to see the website, that’s what
this site is providing.
It’s going to be end of mine day, except before finish
I am reading this enormous paragraph to increase my knowledge.
I couldn’t resist commenting. Exceptionally well written!
Hello, I think your site might be having browser compatibility issues.
When I look at your blog in Chrome, it looks fine but when opening in Internet Explorer, it has some overlapping.
I just wanted to give you a quick heads up!
Other then that, excellent blog!
It’s hard to find well-informed people about this subject,
but you seem like you know what you’re talking about!
Thanks
Your way of telling all in this article is actually fastidious, all can effortlessly be aware
of it, Thanks a lot.
Appreciating the persistence you put into your site and in depth information you provide.
It’s good to come across a blog every once in a while that isn’t the same out of date rehashed information. Wonderful read!
I’ve saved your site and I’m adding your RSS feeds to my Google account.
When someone writes an paragraph he/she maintains the thought of a user in his/her
mind that how a user can know it. Thus that’s why this article is perfect.
Thanks!
Appreciating the dedication you put into your website and detailed information you present.
It’s great to come across a blog every once in a while that isn’t
the same outdated rehashed material. Wonderful read! I’ve saved your site and
I’m including your RSS feeds to my Google account.
I’m not that much of a internet reader to be honest but your blogs really nice, keep it up!
I’ll go ahead and bookmark your website to come back
in the future. Many thanks
What a material of un-ambiguity and preserveness of
precious experience about unpredicted emotions.
Attractive section of content. I just stumbled upon your website and in accession capital to assert that I get actually enjoyed account your blog posts.
Any way I’ll be subscribing to your feeds and even I achievement
you access consistently fast.
Your method of describing the whole thing in this piece of writing is truly pleasant,
all be capable of effortlessly know it, Thanks a lot.
Good ?V I should definitely pronounce, impressed with your web site. I had no trouble navigating through all tabs as well as related info ended up being truly simple to do to access. I recently found what I hoped for before you know it in the least. Quite unusual. Is likely to appreciate it for those who add forums or something, website theme . a tones way for your client to communicate. Nice task..
Having read this I believed it was very informative.
I appreciate you taking the time and energy to put this informative article together.
I once again find myself personally spending way
too much time both reading and commenting. But so what, it was still worthwhile!
This is my first time pay a quick visit at here and i am genuinely impressed to read everthing at one place.
What i don’t realize is actually how you’re now
not actually much more neatly-preferred than you may be right now.
You’re very intelligent. You know therefore significantly when it
comes to this topic, made me personally imagine it from numerous various angles.
Its like women and men are not interested except it is something to accomplish with Girl gaga!
Your own stuffs nice. All the time handle it up!
I like the valuable information you provide in your articles.
I will bookmark your weblog and check again here regularly.
I am quite certain I’ll learn many new stuff right here!
Good luck for the next!
I was able to find good advice from your blog posts.
I’m really impressed with your writing skills
and also with the layout on your blog. Is this a paid theme or did you modify
it yourself? Anyway keep up the excellent quality writing, it’s rare to see a nice blog like this one today.
Awesome blog! Do you have any helpful hints for aspiring
writers? I’m planning to start my own website soon but
I’m a little lost on everything. Would you propose starting
with a free platform like WordPress or go for
a paid option? There are so many options out there that I’m completely confused ..
Any tips? Appreciate it!
Excellent goods from you, man. I have understand
your stuff previous to and you’re just extremely fantastic.
I actually like what you’ve acquired here, really like what you are saying
and the way in which you say it. You make it enjoyable and you still take care of to
keep it wise. I cant wait to read much more from you. This is actually a terrific web site.
Hmm is anyone else experiencing problems with the images on this blog loading?
I’m trying to find out if its a problem on my end or if it’s the blog.
Any suggestions would be greatly appreciated.
I visited a lot of website but I conceive this one has something extra in it in it