【BZOJ 3861】Tree

相关链接

题目传送门: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;
}

13 thoughts to “【BZOJ 3861】Tree”

  1. 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

  2. 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

  3. 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

  4. 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

  5. 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

  6. 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

  7. 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

  8. 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.

发表评论

电子邮件地址不会被公开。 必填项已用*标注