CF981H?K Paths?

題解

一道不錯的分治ntt題目

?

題目稍微轉(zhuǎn)化一下，就是所有k條鏈的存在交，并且交的部分都被覆蓋k次

所以一定是兩個點，之間路徑選擇k次，然后端點兩開花

?

f[x]表示x子樹內(nèi)往下延伸k條鏈（可以停在x）的方案數(shù)（有標號）

每個子樹選擇一個或者不選擇，最多一共選擇k個，dp是O(n^2)的，

考慮生成函數(shù)，其實就是：

而

?

統(tǒng)計答案？

直接兩兩點對f相乘肯定不行，因為f僅僅是子樹

考慮枚舉x作為lca統(tǒng)計

如果是拐彎的鏈，樹形DP即可。

而如果是直上直下的鏈，

對于不同子樹，x的選擇是扣去這個子樹，還可以往上選擇

分治NTT的經(jīng)典問題

const int N=1e5+5; int n,k; int jie[N],inv[N]; int A(int n,int m){if(n<0||m<0||n<m) return 0;return mul(jie[n],inv[n-m]); } int val[N],si[N]; void divi(int l,int r,Poly &f,Poly &g){// cout<<" divi "<<l<<" "<<r<<endl;if(l==r){g.resize(1);g[0]=val[l];f.resize(2);f[0]=1;f[1]=si[l];return;}Poly lf,lg,rf,rg;int mid=(l+r)>>1;divi(l,mid,lf,lg);divi(mid+1,r,rf,rg);f=lf*rf;g=(lf*rg)+(lg*rf); } int f[N],sum[N],son[N]; int ans,sz[N]; struct node{int nxt,to; }e[2*N]; int hd[N],cnt; void add(int x,int y){e[++cnt].nxt=hd[x];e[cnt].to=y;hd[x]=cnt; } void dfs(int x,int fa){// cout<<" xx "<<x<<" fa "<<fa<<endl;sz[x]=1;int pre=0;for(reg i=hd[x];i;i=e[i].nxt){int y=e[i].to;if(y==fa) continue;++son[x];dfs(y,x);sz[x]+=sz[y];sum[x]=ad(sum[x],sum[y]);ans=ad(ans,mul(pre,sum[y]));pre=ad(pre,sum[y]);}if(son[x]){Poly F,G;int ct=0;for(reg i=hd[x];i;i=e[i].nxt){int y=e[i].to;if(y==fa) continue;val[++ct]=sum[y];si[ct]=sz[y];}divi(1,ct,F,G);Poly T;T.resize(2);T[0]=1;T[1]=n-sz[x];G=G*T;for(reg i=0;i<=min(k,son[x]);++i){// cout<<"F["<<i<<"] "<<F[i]<<" G["<<i<<"] "<<G[i]<<endl;ans=ad(ans,mul(A(k,i),G[i]));f[x]=ad(f[x],mul(A(k,i),F[i]));}sum[x]=ad(sum[x],f[x]);}else{f[x]=1;sum[x]=1;}// cout<<" return "<<x<<" f "<<f[x]<<endl; } int main(){rd(n);rd(k);if(k==1){ans=(ll)n*(n-1)/2%mod;ot(ans);return 0;}jie[0]=1;for(reg i=1;i<=k;++i) jie[i]=mul(jie[i-1],i);inv[k]=qm(jie[k],mod-2);for(reg i=k-1;i>=0;--i) inv[i]=mul(inv[i+1],i+1);int x,y;for(reg i=1;i<n;++i){rd(x);rd(y);add(x,y);add(y,x);}dfs(1,0);ot(ans);return 0; }} signed main(){Miracle::main();return 0; }/*Author: *Miracle*Date: 2019/4/8 18:57:00 */

?

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

總結(jié)

以上是生活随笔為你收集整理的CF981H K Paths的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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