群晖做网站,建设工程的招标网站有哪些,网络维护,wordpress 运行时间正题 题目大意 nnn个点的一棵树#xff0c;定义f(S)f(S)f(S)表示点集SSS的生成子图中的边数量。
求∑S∈Vf(S)k\sum_{S\in V}f(S)^kS∈V∑f(S)k 解题思路
因为kkk很小#xff0c;所以可以考虑一下二项式拆解#xff0c;我们需要快速的计算出(ab)k(ab)^k(ab)k#xff0c…正题 题目大意
nnn个点的一棵树定义f(S)f(S)f(S)表示点集SSS的生成子图中的边数量。
求∑S∈Vf(S)k\sum_{S\in V}f(S)^kS∈V∑f(S)k 解题思路
因为kkk很小所以可以考虑一下二项式拆解我们需要快速的计算出(ab)k(ab)^k(ab)k那么就需要求出ai,bi(i≤k)a^i,b^i(i\leq k)ai,bi(i≤k)。
那么我们可以设f0/1,i,jf_{0/1,i,j}f0/1,i,j表示点iii是否被选择时f(S)jf(S)^jf(S)j的答案。
这样我们可以做到O(k2)O(k^2)O(k2)从yyy转移到xxx。具体的对于f0,x,if_{0,x,i}f0,x,i我们把它和f0,y,if1,y,if_{0,y,i}f_{1,y,i}f0,y,if1,y,i卷起来。对于f1,x,if_{1,x,i}f1,x,i我们先把f1,y,if_{1,y,i}f1,y,i和111卷起来然后同上。
时间复杂度O(nk2)O(nk^2)O(nk2) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510,XJQ998244353;
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].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dp(int x,int fa){f[0][x][0]f[1][x][0]1;for(int pls[x];p;pa[p].next){int ya[p].to;if(yfa)continue;dp(y,x);for(int i0;ik;i)tmp[2][i]f[1][y][i];for(int i0;ik;i){tmp[3][i]0;for(int j0;ji;j)(tmp[3][i]1ll*tmp[2][j]%XJQ*c[i][j]%XJQ)%XJQ;}for(int i0;ik;i)tmp[0][i]f[0][x][i],tmp[1][i]f[1][x][i];for(int i0;ik;i){f[0][x][i]f[1][x][i]0;for(int j0;ji;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 i1;im;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}c[0][0]1;for(int i1;ik;i)for(int j0;ji;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;
}
