解析

比較巧妙的一道題。
難點(diǎn)在于對(duì)題意的轉(zhuǎn)化。

關(guān)鍵性質(zhì)：符合要求的點(diǎn)等價(jià)于與笛卡爾樹(shù)上深度為 $m$ 的點(diǎn)。

原因也較為顯然，考慮一個(gè)特定的點(diǎn) $x$，當(dāng)枚舉全局最大值時(shí)，其會(huì)對(duì) $x$ 產(chǎn)生貢獻(xiàn)，且最大值另一側(cè)就和 $x$ 沒(méi)有關(guān)系了，向有 $x$ 的一側(cè)遞歸尋找最大值計(jì)算貢獻(xiàn)，這個(gè)過(guò)程和笛卡爾樹(shù)的構(gòu)造是一樣的。

問(wèn)題就轉(zhuǎn)化為了：給定一個(gè)二叉樹(shù)，求第 $m$ 層有 $k$ 個(gè)節(jié)點(diǎn)的方案數(shù)。
這就是一個(gè)喜聞樂(lè)見(jiàn)的dp了。
設(shè)計(jì)狀態(tài) $d{p}_{i,j,s}$ 表示子樹(shù)根節(jié)點(diǎn)深度為 $j$，子樹(shù)大小為 $i$，且子樹(shù)內(nèi)有 $s$ 個(gè)好點(diǎn)的方案數(shù)。
就有轉(zhuǎn)移：
$$f_{i,j,s}=\sum _{a=0}^{i?1}\sum _{b=0}^a\left(\genfrac{}{}{0ex}{}{i?1}{a}\right)f_{a,j+1,b}\times f_{i?1?a,j+1,s?b?[j=m]}$$
直接做是 $O(n^5)$ 的。
然后似乎也沒(méi)有什么辦法優(yōu)化這個(gè)東西…于是就卡一卡常好了，調(diào)整一些變量的枚舉上界，再直接讓 $f_{i,m,1}=i!$。
然后就能卡過(guò)去了，最慢的點(diǎn) $1.7s$。
（真不理解出題人為什么不能把范圍改成 $80$ 之類(lèi)的，這種東西比賽時(shí)就算想到了也很可能不敢寫(xiě)吧…）

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") using namespace std;const int N=105;inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int mod;inline ll ksm(ll x,ll k){ll res(1);while(k){if(k&1) res=res*x%mod;x=x*x%mod;k>>=1;}return res; }int n,m,cnt; ll c[N][N],jc[N]; void init(int n){c[0][0]=1;for(int i=1;i<=n;i++){c[i][0]=1;for(int j=1;j<=i;j++){c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}}jc[0]=1;for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;return; } ll f[N][N][N];signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifn=read();m=read();cnt=read();mod=read();init(n);for(int i=0;i<=n;i++) f[i][m][min(i,1)]=jc[i];for(int j=m-1;j>=1;j--){f[0][j][0]=1;for(int i=1;i+(j-1)<=n;i++){for(int k=0;k<=min(cnt,i);k++){for(int a=0;a<i;a++){for(int b=0;b==0||b+m-(j+1)<=a;b++){(f[i][j][k]+=f[a][j+1][b]*f[i-1-a][j+1][k-b]%mod*c[i-1][a])%=mod;//printf("(%d %d %d) -< (%d %d %d)*(%d %d %d) add=%lld\n",i,j,k,a,j+1,b,i-1-a,j+1,m-)}}}}}//for(int j=1;j<=m;j++){// for(int i=0;i<=n;i++){// for(int k=0;k<=cnt;k++) printf("siz=%d dep=%d num=%d f=%lld\n",i,j,k,f[i][j][k]);// }//}printf("%lld\n",f[n][1][cnt]);return 0; } /* */

總結(jié)

以上是生活随笔為你收集整理的CF1580B Mathematics Curriculum（笛卡尔树、树形dp）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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