# 【BZOJ 3861】Tree

Claris还给出了一个方法：

### 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];

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 i=1;i<=n;i++) {
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;
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. 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

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

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

4. 480785 882231I truly enjoy examining on this internet site , it has very good content . 437117

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

6. 545193 204840You need to indulge in a contest for among the greatest blogs over the internet. Ill suggest this internet website! 886251

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

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

9. 814291 423823Really instructive and great bodily structure of subject matter, now thats user pleasant (:. 148366

10. 255322 454636I want going to comment as this posts a bit old now, but just wanted to say thanks. 85949

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

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

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