【BZOJ 3861】Tree









#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++) 
		if (tag) {printf("Case #%d: 0\n",tot); continue;}
		int p = 1, w = 0, vout = 0; 
		f[p][0] = 1;
		for (int i=1;i<=n;++i,p^=1,w^=1) {
			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.


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