正題

---

題目大意

$n$個點的一棵樹，定義$f(S)$表示點集$S$的生成子圖中的邊數量。

求$$\sum _{S\in V}f(S{)}^k$$

---

解題思路

因為$k$很小，所以可以考慮一下二項式拆解，我們需要快速的計算出$(a+b{)}^k$，那么就需要求出$a^i,b^i(i\le k)$。

那么我們可以設$f_{0/1,i,j}$表示點$i$是否被選擇時$f(S{)}^j$的答案。

這樣我們可以做到$O(k^2)$從$y$轉移到$x$。具體的，對于$f_{0,x,i}$，我們把它和$f_{0,y,i}+f_{1,y,i}$卷起來。對于$f_{1,x,i}$，我們先把$f_{1,y,i}$和$1$卷起來，然后同上。

時間復雜度$O(n{k}^2)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10,XJQ=998244353; struct node{int to,next; }a[N*2]; int n,k,tot,m,ls[N],f[2][N][12],c[11][12],tmp[4][12]; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dp(int x,int fa){f[0][x][0]=f[1][x][0]=1;for(int p=ls[x];p;p=a[p].next){int y=a[p].to;if(y==fa)continue;dp(y,x);for(int i=0;i<=k;i++)tmp[2][i]=f[1][y][i];for(int i=0;i<=k;i++){tmp[3][i]=0;for(int j=0;j<=i;j++)(tmp[3][i]+=1ll*tmp[2][j]%XJQ*c[i][j]%XJQ)%=XJQ;}for(int i=0;i<=k;i++)tmp[0][i]=f[0][x][i],tmp[1][i]=f[1][x][i];for(int i=0;i<=k;i++){f[0][x][i]=f[1][x][i]=0;for(int j=0;j<=i;j++){(f[0][x][i]+=1ll*tmp[0][i-j]*(f[0][y][j]+f[1][y][j])%XJQ*c[i][j]%XJQ)%=XJQ;(f[1][x][i]+=1ll*tmp[1][i-j]*(tmp[3][j]+f[0][y][j])%XJQ*c[i][j]%XJQ)%=XJQ;}}}return; } int main() {freopen("subgraph.in","r",stdin); // freopen("subgraph.out","w",stdout);scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}c[0][0]=1;for(int i=1;i<=k;i++)for(int j=0;j<=i;j++){c[i][j]=c[i-1][j];if(j)(c[i][j]+=c[i-1][j-1])%=XJQ;}dp(1,0);printf("%d\n",(f[0][1][k]+f[1][1][k])%XJQ);return 0; }

總結

以上是生活随笔為你收集整理的jzoj5702-[gdoi2018day2]滑稽子图【树形dp,二项式定理】的全部內容，希望文章能夠幫你解決所遇到的問題。

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