【学习笔记】「2020-2021 集训队作业」Communication Network

有点难😅

发现容斥系数设计的非常巧妙🤔

设$f(i)$表示恰好有$i$条边相同的方案数，$g(i)$表示至少有$i$条边相同的方案数

根据二项式反演，$g(i)={\sum }_{j\ge i}\left(\genfrac{}{}{0ex}{}{j}{i}\right)f(j)\Rightarrow f(i)={\sum }_{j\ge i}(-1{)}^{j-i}(\genfrac{}{}{0ex}{}{j}{i})g_j$

这个式子成立是因为$[i=j]={\sum }_{j\le k\le i}(-1{)}^{k-j}(\genfrac{}{}{0ex}{}{i}{k}\left)\right(\genfrac{}{}{0ex}{}{k}{j})$，点这里

用$g(i)$进行替换，答案是$\sum g(j)\cdot ({\sum }_{i\le j}i\cdot 2^i\cdot (-1{)}^{j-i}\cdot \left(\genfrac{}{}{0ex}{}{j}{i}\right))$

发现后面那一坨就等于$2j$。又根据$\text{prufer}$序列，对于$k$个连通块的生成树的方案数为$n^{k-2}\prod s_i$，可以转化为在每个连通块中钦定选一个点以及在选的边中钦定选一条边的方案数，这样就做完了。

类似的题目：CF1842G Tenzing and Random Operations

复杂度$O(n)$。

#include
#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 mod=998244353;
const int N=2e6+5;
int n;
ll dp[N][2][2];
vector<int>G[N];
ll fpow(ll x,ll y=mod-2){
    ll z(1);
    for(;y;y>>=1){
        if(y&1)z=z*x%mod;
        x=x*x%mod;
    }return z;
}
void add(ll &x,ll y){
    x=(x+y)%mod;
}
void dfs(int u,int topf){
    dp[u][0][0]=dp[u][1][0]=1;
    for(auto v:G[u]){
        if(v==topf)continue;
        dfs(v,u),memset(dp[0],0,sizeof dp[0]);
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    for(int l=0;l<2;l++){
                        if(j==1&&l==1)continue;
                        if(i==0||k==0){
                            add(dp[0][i+k][j+l],dp[u][i][j]*dp[v][k][l]);
                            if(j==0&&l==0)add(dp[0][i+k][1],dp[u][i][j]*dp[v][k][l]);
                        }
                        if(k==1){
                            add(dp[0][i][j+l],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);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        G[x].pb(y),G[y].pb(x);
    }dfs(1,0)
    ll res=dp[1][1][1]*fpow(n,mod-2)%mod*2%mod;
    cout<<(res+mod)%mod;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58