网站有备案 去掉备案,触屏网站开发教程,网站开发石家庄,文件管理系统题目链接
CF方向 Luogu方向
题目解法
首先一个套路是普通幂转下降幂#xff08;为什么#xff1f;因为观察到 k k k 很小#xff0c;下降幂可以转化组合数问题#xff0c;从而 d p dp dp 求解#xff09; 即 f ( X ) k ∑ i 0 k { k i } i ! ( f ( X ) i ) f(X)^k…题目链接
CF方向 Luogu方向
题目解法
首先一个套路是普通幂转下降幂为什么因为观察到 k k k 很小下降幂可以转化组合数问题从而 d p dp dp 求解 即 f ( X ) k ∑ i 0 k { k i } i ! ( f ( X ) i ) f(X)^k\sum\limits_{i0}^{k}{k\brace i}i!\binom{f(X)}{i} f(X)ki0∑k{ik}i!(if(X)) 现在的问题是对于所有生成树求出中间选 i i i 条边的方案数
我们令非空顶点的点集为关键点其他生成树上的点为包含点 考虑树形 d p dp dp令 f i , j f_{i,j} fi,j 表示在 i i i 的子树中选出至少 1 1 1 个关键点且与 i i i 连通的生成树中选出 j j j 条边的方案数 考虑转移 v v v 子树中没有关键点 f u , i → f u , i f_{u,i}\to f_{u,i} fu,i→fu,i不能计入答案计算因为没有改变关键点集合只有 v v v 子树中的关键点组成 f v , i f v , i − 1 → f u , i f_{v,i}f_{v,i-1}\to f_{u,i} fv,ifv,i−1→fu,i不能计入答案计算因为这个关键点集合在 v v v 时已经计算过 u , v u,v u,v 子树中均有关键点 f u , i ∗ f v , j → f u , i j f u , i j 1 f_{u,i}*f_{v,j}\to f_{u,ij}\f_{u,ij1} fu,i∗fv,j→fu,ijfu,ij1可以计入答案计算因为改变了关键点集合
根据树形 d p dp dp 的时间复杂度计算时间复杂度为 O ( n k ) O(nk) O(nk)
#include bits/stdc.h
using namespace std;
const int N100100,K210,P1e97;
int n,k,siz[N],s2[K][K],t[N],ans[N];
int ne[N1],e[N1],h[N],idx;
int f[N][K];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
inline void add(int x,int y){ e[idx]y,ne[idx]h[x],h[x]idx;}
inline void inc(int x,int y){ xy;if(xP) x-P;}
void dfs(int u,int fa){siz[u]1,f[u][0]1;for(int ih[u];~i;ine[i]){int ve[i];if(vfa) continue;dfs(v,u);for(int j0;jk;j) t[j]f[u][j];for(int j0;jk;j){inc(t[j],f[v][j]);if(j) inc(t[j],f[v][j-1]);}for(int p0,mxpmin(k,siz[u]);pmxp;p) for(int q0,mxqmin(k-p,siz[v]);qmxq;q){int coef1ll*f[u][p]*f[v][q]%P;inc(t[pq],coef),inc(t[pq1],coef);inc(ans[pq],coef),inc(ans[pq1],coef);}siz[u]siz[v];for(int j0;jk;j) f[u][j]t[j];}
}
int main(){nread(),kread();s2[0][0]1;for(int i1;ik;i) for(int j1;ji;j) s2[i][j](s2[i-1][j-1]1ll*s2[i-1][j]*j)%P;memset(h,-1,sizeof(h));for(int i1;in;i){int xread(),yread();add(x,y),add(y,x);}dfs(1,-1);int ANS0;for(int i1,fac1;ik;i,fac1ll*fac*i%P) ANS(ANS1ll*ans[i]*s2[k][i]%P*fac)%P;printf(%d\n,ANS);return 0;
}
