根据网站集约化建设要求,网站的外部链接怎么做,简单 网站设计,建设部招标网站题目链接
CF方向 Luogu方向
题目解法
一个显然的转化是#xff1a;恰好 k k k 条边不好求#xff0c;所以把 恰好 转化成 至少#xff0c;然后进行二项式反演 令 f i f_i fi 为恰好 k k k 条边 . . . ... ...#xff0c; g i g_i gi 为至少 k k k 条边 . . . …题目链接
CF方向 Luogu方向
题目解法
一个显然的转化是恰好 k k k 条边不好求所以把 恰好 转化成 至少然后进行二项式反演 令 f i f_i fi 为恰好 k k k 条边 . . . ... ... g i g_i gi 为至少 k k k 条边 . . . ... ... 那么 f i ∑ j i n − 1 g j ( − 1 ) j − i ( j i ) f_i\sum\limits_{ji}^{n-1}g_j(-1)^{j-i}\binom{j}{i} fiji∑n−1gj(−1)j−i(ij) 这一部分的时间复杂度是 O ( n 2 ) O(n^2) O(n2) 的
考虑求解 g g g可以发现保留的边数和连通块个数是可以对应的所以接下来只对连通块考虑 这里有一个结论是如果 m m m 个连通块的大小分别是 s i z 1 , s i z 2 , . . . , s i z m siz_1,siz_2,...,siz_m siz1,siz2,...,sizm且每个点都有编号则把它们构成生成树的方案数为 n m − 2 ∏ s i z i n^{m-2}\prod siz_i nm−2∏sizi 证明可以见 oiwiki-prufer 中的 图连通方案数
我们发现直接把上面的式子进行 d p dp dp 的时间复杂度是 O ( n 3 ) O(n^3) O(n3) 的即令 d p i , j , k dp_{i,j,k} dpi,j,k 表示在 i i i 的子树中选出了 j j j 个连通块 i i i 所在连通块有 k k k 个点的方案数
我们考虑 ∏ s i z i \prod siz_i ∏sizi 的组合意义即在每个连通块中选出一个点的方案数 这样就可以令 d p i , j , 0 / 1 dp_{i,j,0/1} dpi,j,0/1 表示在 i i i 的子树中选出了 j j j 个连通块 i i i 所在连通块是否选过点的方案数 转移比较好转移根据背包 d p dp dp 的时间复杂度分析可以做到 O ( n 2 ) O(n^2) O(n2)
#include bits/stdc.h
using namespace std;
const int N110,P1e97;
typedef long long LL;
int n,g[N],f[N],C[N][N];
int dp[N][N][2],t[N][2],siz[N];
int e[N1],ne[N1],h[N],idx;
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 inc(int x,LL y){x(xy)%P;if(x0) xP;
}
void dfs(int u,int fa){dp[u][1][0]dp[u][1][1]1,siz[u]1;for(int ih[u];~i;ine[i]){int ve[i];if(vfa) continue;dfs(v,u);for(int j1;jsiz[u]siz[v];j) t[j][0]t[j][1]0; for(int j1;jsiz[u];j) for(int k1;ksiz[v];k){inc(t[jk][0],1ll*dp[u][j][0]*dp[v][k][1]);inc(t[jk][1],1ll*dp[u][j][1]*dp[v][k][1]);inc(t[jk-1][0],1ll*dp[u][j][0]*dp[v][k][0]);inc(t[jk-1][1],(1ll*dp[u][j][0]*dp[v][k][1]1ll*dp[u][j][1]*dp[v][k][0]));}siz[u]siz[v];for(int j1;jsiz[u];j) dp[u][j][0]t[j][0],dp[u][j][1]t[j][1];}
}
void add(int x,int y){ e[idx]y,ne[idx]h[x],h[x]idx;}
int qmi(int a,int b){if(b0) return qmi(a,P-2);int res1;for(;b;b1){if(b1) res1ll*res*a%P;a1ll*a*a%P;}return res;
}
int main(){nread();memset(h,-1,sizeof(h));for(int i1;in;i){int xread(),yread();add(x,y),add(y,x);}dfs(1,-1);for(int i1;in;i) g[n-i]1ll*dp[1][i][1]*qmi(n,i-2)%P;C[0][0]1;for(int i1;in;i) for(int j0;ji;j) C[i][j](!j||ij)?1:(C[i-1][j-1]C[i-1][j])%P;for(int i0;in;i)for(int ji,neg1;jn;j,neg*-1)inc(f[i],1ll*g[j]*neg*C[j][i]);for(int i0;in;i) printf(%d ,f[i]);puts();fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
/*
f[i][j][0/1]: 在i的子树中分成了j个连通块i连通块内是否选过的方案数
*/
