相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3861
数据生成器:http://paste.ubuntu.com/23863232/
神犇题解:http://www.cnblogs.com/clrs97/p/6329731.html
解题报告
因为每一个数会且仅会出现在一个集合中
于是我们就可以很方便地容斥辣!
时间复杂度:$O(n^2)$
Claris还给出了一个方法:
将可以匹配的集合与点连边,这样的话,就搞出一个二分图
于是答案就是统计这个二分图完备匹配的个数
因为这个二分图性质很特殊,于是也是可以DP哒!
时间复杂度:$O(n^2)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 1009; const int MOD = 1000000007; int n,cnt[N],f[2][N],POW[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 Pow(int w, int t) { int ret = 1; while (t) { if (t & 1) ret = (LL)ret * w % MOD; w = (LL)w * w % MOD; t >>= 1; } return ret; } int main() { POW[0] = 1; for (int i=1;i<N;i++) POW[i] = (LL)POW[i-1] * i % MOD; for (int tag=0,tot=1,spj=0;n=read();tag=spj=0,++tot) { for (int i=1;i<=n;i++) { cnt[i] = read(); if (cnt[i] == n) tag = 1; if (!cnt[i]) spj++; for (int j=1;j<=cnt[i];j++) read(); } if (tag) {printf("Case #%d: 0\n",tot); continue;} int p = 1, w = 0, vout = 0; memset(f[p],0,sizeof(f[p])); f[p][0] = 1; for (int i=1;i<=n;++i,p^=1,w^=1) { memset(f[w],0,sizeof(f[w])); f[w][0] = f[p][0]; for (int j=1;j<=n;j++) { (f[w][j] += f[p][j]) %= MOD; (f[w][j] += (LL)f[p][j-1] * cnt[i] % MOD) %= MOD; } } for (int i=0,t=1;i<=n;i++,t*=-1) { f[p][i] = (LL)f[p][i] * POW[n-i] % MOD; (vout += f[p][i] * t) %= MOD; } vout = (LL)vout * Pow(POW[spj], MOD-2) % MOD; printf("Case #%d: %d\n",tot,(vout+MOD)%MOD); } return 0; }
651450 516386Intersting post and web site. Great that Google listed so i was able to get here. This internet site will go no in my bookmarks from now. 103331
261896 806590Aw, this was a extremely good post. In thought I wish to put in writing like this furthermore – taking time and precise effort to make an exceptional article but what can I say I procrastinate alot and under no circumstances seem to get something done. 744670
807251 519557Hello, Neat post. There is an problem along along with your website in internet explorer, may well test thisK IE nonetheless may be the marketplace chief and a big section of people will pass over your outstanding writing due to this difficulty. 493866
480785 882231I truly enjoy examining on this internet site , it has very good content . 437117
201417 355908Spot on with this write-up, I must say i believe this outstanding site needs much a lot more consideration. Ill probably be once again to learn a terrific deal a lot more, many thanks that information. 528449
545193 204840You need to indulge in a contest for among the greatest blogs over the internet. Ill suggest this internet website! 886251
752674 354465View the following tips less than and discover to know how to observe this situation whilst you project your home business today. Earn dollars from home 439306
148785 103213Water-resistant our wales in advance of when numerous planking. The particular wales surely are a selection of heavy duty snowboards that this height ones would be exactly the same in principle as a new shell planking having said that with a lot a lot more height to assist you thrust outward inside the evening planking. planking 239545
814291 423823Really instructive and great bodily structure of subject matter, now thats user pleasant (:. 148366
255322 454636I want going to comment as this posts a bit old now, but just wanted to say thanks. 85949
47397 857704Its a shame you dont have a donate button! Id most certainly donate to this outstanding internet site! I suppose within the meantime ill be pleased with bookmarking and putting your Rss feed to my Google account. I look forward to fresh updates and will share this blog with my Facebook group: ) 773587
205643 539704Spot up for this write-up, I really believe this web site requirements a terrific deal a lot more consideration. Ill likely to end up once more to read a great deal more, numerous thanks for that information. 931492
I will right away snatch your rss feed as I can’t in finding your e-mail subscription hyperlink or newsletter service. Do you have any? Please permit me know so that I may just subscribe. Thanks.
This site is my breathing in, really superb pattern and perfect subject matter.