企业网站设计制作价格,在WordPress,怎么做织梦网站,免费制作企业小程序有点难#x1f605;
发现容斥系数设计的非常巧妙#x1f914;
设 f ( i ) f(i) f(i)表示恰好有 i i i条边相同的方案数#xff0c; g ( i ) g(i) g(i)表示至少有 i i i条边相同的方案数
根据二项式反演#xff0c; g ( i ) ∑ j ≥ i ( j i ) f ( j ) ⇒ f ( i ) ∑ j…有点难
发现容斥系数设计的非常巧妙
设 f ( i ) f(i) f(i)表示恰好有 i i i条边相同的方案数 g ( i ) g(i) g(i)表示至少有 i i i条边相同的方案数
根据二项式反演 g ( i ) ∑ j ≥ i ( j i ) f ( j ) ⇒ f ( i ) ∑ j ≥ i ( − 1 ) j − i ( j i ) g j g(i)\sum_{j\ge i}\binom{j}{i}f(j)\Rightarrow f(i)\sum_{j\ge i}(-1)^{j-i}\binom{j}{i}g_j g(i)∑j≥i(ij)f(j)⇒f(i)∑j≥i(−1)j−i(ij)gj
这个式子成立是因为 [ i j ] ∑ j ≤ k ≤ i ( − 1 ) k − j ( i k ) ( k j ) [ij]\sum_{j\le k\le i}(-1)^{k-j}\binom{i}{k}\binom{k}{j} [ij]∑j≤k≤i(−1)k−j(ki)(jk)点这里
用 g ( i ) g(i) g(i)进行替换答案是 ∑ g ( j ) ⋅ ( ∑ i ≤ j i ⋅ 2 i ⋅ ( − 1 ) j − i ⋅ ( j i ) ) \sum g(j)\cdot (\sum_{i\le j}i\cdot 2^i\cdot (-1)^{j-i}\cdot \binom{j}{i}) ∑g(j)⋅(∑i≤ji⋅2i⋅(−1)j−i⋅(ij))
发现后面那一坨就等于 2 j 2j 2j。又根据 prufer \text{prufer} prufer序列对于 k k k个连通块的生成树的方案数为 n k − 2 ∏ s i n^{k-2}\prod s_i nk−2∏si可以转化为在每个连通块中钦定选一个点以及在选的边中钦定选一条边的方案数这样就做完了。
类似的题目CF1842G Tenzing and Random Operations
复杂度 O ( n ) O(n) O(n)。
#includebits/stdc.h
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define ull unsigned long long
#define inf 0x3f3f3f3f
using namespace std;
const int mod998244353;
const int N2e65;
int n;
ll dp[N][2][2];
vectorintG[N];
ll fpow(ll x,ll ymod-2){ll z(1);for(;y;y1){if(y1)zz*x%mod;xx*x%mod;}return z;
}
void add(ll x,ll y){x(xy)%mod;
}
void dfs(int u,int topf){dp[u][0][0]dp[u][1][0]1;for(auto v:G[u]){if(vtopf)continue;dfs(v,u),memset(dp[0],0,sizeof dp[0]);for(int i0;i2;i){for(int j0;j2;j){for(int k0;k2;k){for(int l0;l2;l){if(j1l1)continue;if(i0||k0){add(dp[0][ik][jl],dp[u][i][j]*dp[v][k][l]);if(j0l0)add(dp[0][ik][1],dp[u][i][j]*dp[v][k][l]);}if(k1){add(dp[0][i][jl],dp[u][i][j]*dp[v][k][l]%mod*n);}}}}}memcpy(dp[u],dp[0],sizeof dp[0]);}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinn;for(int i1;in;i){int x,y;cinxy;G[x].pb(y),G[y].pb(x);}dfs(1,0)ll resdp[1][1][1]*fpow(n,mod-2)%mod*2%mod;cout(resmod)%mod;
}
