首先考慮無解的情況， 根據(jù)purfer序列，當(dāng)dee[i]=0并且n!=1的時候，必然無解。否則為1.

且sum(dee[i]-1)!=n-2也必然無解。

剩下的使用排列組合即可推出公式。需要注意的是題目雖然說最終答案不會超過1e17，但是中間過程可能超。

由于n<=150, 所以sum最多是148. 于是我們可以打出150*150的組合表。實(shí)現(xiàn)O(1)計算組合數(shù)。

?

# include <cstdio> # include <cstring> # include <cstdlib> # include <iostream> # include <vector> # include <queue> # include <stack> # include <map> # include <set> # include <cmath> # include <algorithm> using namespace std; # define lowbit(x) ((x)&(-x)) # define pi 3.1415926535 # define eps 1e-9 # define MOD 100000007 # define INF 1000000000 # define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r # define mp make_pair # define pb push_back typedef pair<int,int> PII; typedef vector<int> VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; int Scan() {int res=0, flag=0;char ch;if((ch=getchar())=='-') flag=1;else if(ch>='0'&&ch<='9') res=ch-'0';while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch-'0');return flag?-res:res; } void Out(int a) {if(a<0) {putchar('-'); a=-a;}if(a>=10) Out(a/10);putchar(a%10+'0'); } const int N=10005; //Code begin...int dee[155]; LL cc[155][155];void init() {FOR(i,0,150) {cc[i][0]=1;FOR(j,1,i) cc[i][j]=cc[i-1][j-1]+cc[i-1][j];} } int main () {init();int n, sum=0;LL ans=1;scanf("%d",&n);if (n==1) {scanf("%d",dee);puts(dee[0]==0?"1":"0");return 0;}FOR(i,1,n) {scanf("%d",dee+i), --dee[i], sum+=dee[i];if (dee[i]<0) {puts("0"); return 0;}}if (sum!=n-2) {puts("0"); return 0;}FOR(i,1,n) {if (!dee[i]) continue;ans*=cc[sum][dee[i]];sum-=dee[i];}printf("%lld\n",ans);return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/lishiyao/p/6543647.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1211 树的计数(purfer序列)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。