正題

題目鏈接:https://jzoj.net/senior/#main/show/2755

---

題目大意

求有多少個$n$個點直徑為$d$的標號樹。

---

解題思路

定義$f_{i,j}$表示$i$個點，深度不超過$j$的標號樹數量。

然后有轉移$$f_{i,j}=\sum _{k=1}^{i?1}{C}_{i?2}^{k?1}?k?f_{k,j?1}?f_{i?k,j}$$

然后對于輸入，我們考慮根節點就是直徑經過的點，那么我們分為兩種情況討論

$d$是奇數，這個我們枚舉兩個樹拼接在一起然后其它的點瞎連接即可

$d$是偶數，將兩棵樹拼接在一起即可，那么答案為$f_{n,d/2}?f_{n,d/2+1}?$我們發現會有不合法情況，把不合法情況減去就好了

要高精度

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=51,P=1e6; struct BNN{ll a[N],siz; }ans,c[N][N],f[N][N],tmp; BNN operator+(BNN a,BNN b){for(ll i=0;i<N;i++){a.a[i]=a.a[i]+b.a[i];a.a[i+1]+=a.a[i]/P;a.a[i]%=P;if(a.a[i])a.siz=i;}return a; } BNN operator-(BNN a,BNN b){for(ll i=0;i<N;i++){a.a[i]=a.a[i]-b.a[i];while(a.a[i]<0){a.a[i+1]--;a.a[i]+=P;}if(a.a[i])a.siz=i;}return a; } BNN operator*(BNN a,BNN b){BNN c;memset(c.a,0,sizeof(c.a));for(ll i=0;i<=a.siz;i++)for(ll j=0;j<=b.siz;j++)c.a[i+j]+=a.a[i]*b.a[j];c.siz=0;for(ll i=0;i<N;i++){c.a[i+1]+=c.a[i]/P;c.a[i]%=P;if(c.a[i])c.siz=i;}return c; } void write(BNN x){ll w=N-1;while(w&&!x.a[--w]);printf("%lld",x.a[w]);while((--w)>=0){if(x.a[w]<1e5)putchar('0');if(x.a[w]<1e4)putchar('0');if(x.a[w]<1e3)putchar('0');if(x.a[w]<1e2)putchar('0');if(x.a[w]<1e1)putchar('0');printf("%lld",x.a[w]);}putchar('\n'); } int main() {c[0][0].a[0]=1;for(ll i=1;i<N;i++){c[i][0].a[0]=1;for(ll j=1;j<=i;j++)c[i][j]=c[i-1][j]+c[i-1][j-1];}for(ll i=0;i<N;i++)f[1][i].a[0]=1;for(ll n=2;n<N;n++) for(ll d=1;d<N;d++){if(d>=n) {f[n][d]=f[n][d-1];continue;}for(ll i=1;i<n;i++){tmp.a[0]=i;f[n][d]=f[n][d]+(c[n-2][i-1]*tmp*f[i][d-1]*f[n-i][d]);n++;n--; }}ll n,d;while(scanf("%lld%lld",&n,&d)!=EOF){ll r=d/2;if(n==d){printf("0\n");continue;}if(!d){printf("%lld\n",(n==1));continue;}if(!r){printf("%lld\n",(n==2));continue;}memset(ans.a,0,sizeof(ans.a));ans.siz=0;if(d&1){for(ll i=r;i<n;i++){ll j=n-2-i;if(j<r) continue;ans=ans+((f[i+1][r]-f[i+1][r-1])*(f[j+1][r]-f[j+1][r-1])*c[n-2][i]);}ans=ans*c[n][2];}else{ans=f[n][r]-f[n][r-1];if(r>=2){for(ll i=r;i<=n-1;i++){tmp.a[0]=i;ans=ans-(tmp*(f[i][r-1]-f[i][r-2])*c[n-1][i]*f[n-i][r-1]);}}tmp.a[0]=n;ans=ans*tmp;}write(ans);} } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的jzoj2755-[2012东莞市选]树的计数【dp,高精度】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。