题解：P14270 ABC253Ex 加强版

· · 题解

P14270

尽量通俗一点。可能很多地方不太标准。

首先转边集计数为点集计数，记 f(S) 表示点集 S​ 形成一棵树的方案数。

计算 f(S)

显然可以矩阵树定理，做到 O(2^nn^3)，但是太没有美感了，并且复杂度过高。

我们按照点的编号从小到大加入，每次加入 x 会把之前的若干个树拼起来。

假设当前连接的若干树的点集为 T_1,T_2,\dots,T_p，c_{T_i} 表示 T_i 中的点和 x 连边数量之和。

此时 c_i 跟 T_i 如何形成一棵树没有关系，这给我们用哈集幂计算提供可能。

显然，c_i 也表示把 T_i 接在 x 上的方案数。

即当前方案数为 \prod_{i=1}^{p}c_{T_i}，再拼上每棵树的方案 f(T_i)，则一棵树的方案数为 \prod f(T_i)c_{T_i}。

设 g(T)=f(T)c_T，则此时总方案数

\sum_{T1,T2,\dots,T_p}\prod_{i=1}^{p}g(T_i)

不难发现，这个就是 \exp(S) 的组合意义，所以我们对 g 做一遍 \exp 即可。

对于每一个 x 做一遍大小为 2^{x-1} 的 \exp，复杂度 O(\sum_{i=1}^{n}2^{i-1}(i-1)^2)。

引入：dp 计算多项式复合

考虑一个集合幂级数 F(S)，其中 S\in[0,2^n)，数组 a_i，i\in[0,n]。

现在我们要计算

\sum_{i=0}^{n}a_i\frac{F(S)^i}{i!}

定义集合 T 的权值为 F(T)。

考虑第 i 项对答案提供 [x^S] 的意义：将 S 拆成 i 个两两不交，互不区分的子集，权值积之和。

可以考虑 dp，套路地定义子集加入顺序为按照 \max(S) 加入。

定义 f_{i,j,S} 表示当前考虑到第 i 个元素，仍然需要加入 j 个集合，当前集合为 S 的权值和。

转移考虑是否加入包含第 i 个元素的集合。

第一种转移中 S,T 均只可能包含 1 到 i-1 种元素。

初始状态 f_{0,i,\emptyset }=a_i，表示给 F(S)^i 一个初始权值。

用子集卷积转移，复杂度 O(\sum_{i=1}^{n}(n-i)(i-1)^22^{i-1})。

这个做法叫逐点牛顿迭代法，但是我没看出哪里牛顿迭代。

::::success[Code]

inline void juan(int*A,int*B,int*C,int lim){
    for(int i=0;i<=lim;i++)for(int S=0;S<(1<<lim);S++)P[i][S]=Q[i][S]=R[i][S]=0;
    for(int S=0;S<(1<<lim);S++){
        P[pc(S)][S]=A[S],Q[pc(S)][S]=B[S];
    }
    for(int i=0;i<=lim;i++)FWT(P[i],lim),FWT(Q[i],lim);
    for(int S=0;S<(1<<lim);S++){
        for(int i=0;i<=lim;i++)for(int j=0;i+j<=lim;j++){
            (R[i+j][S]+=P[i][S]*Q[j][S]%mod)%=mod;
        }
    }
    for(int i=0;i<=lim;i++)IWT(R[i],lim);
    for(int S=0;S<(1<<lim);S++)C[S]=R[pc(S)][S];
}
int fac[MAXN];
inline void comp(int*G,int*F,int*Ans){
    static int*f[MAXN][MAXN],vl[MAXS],tmp[MAXS];
    for(int i=0;i<=n;i++)for(int j=0;j<=n-i;j++){
        f[i][j]=new int[1<<i];
    }
    for(int i=0;i<=n;i++){
        f[0][i][0]=G[i]*fac[i]%mod;
    }
    for(int i=1;i<=n;i++)for(int j=0;j<=n-i;j++){
        for(int S=0;S<(1<<i-1);S++)vl[S]=F[S|(1<<i-1)];
        juan(vl,f[i-1][j+1],tmp,i-1);
        for(int S=0;S<(1<<i-1);S++){
            f[i][j][S]=f[i-1][j][S];
            f[i][j][S|(1<<i-1)]=tmp[S];
        }
    }
    for(int S=0;S<(1<<n);S++)Ans[S]=f[n][0][S];
}

::::

重设计 dp

现在看回这道题。加入 i 条边之后会形成 n-i 个连通块。

考虑上加边顺序的方案数后，加入 i 条边的答案即为 i!\times [x^U]F(S)^{n-i}。

所以只需考虑 [x^U]F(S)^k 怎么快速求。

对于刚才那个 dp，最后需要记录当前集合，但是此时不关心 S 由几个集合拼起来。

对于现在的 dp，最后关心 S 由几个集合拼起来，但是因为只需要 x^U 的系数，所以不用记录当前集合。

发现完全就是相反的，我们把 dp 倒过来做一遍就可以了。

状态定义改为：当前考虑到第 i 个数，此时删去了 j 个集合，剩下了 S 的权值和。

转移类似，每次枚举 \max(S)=i 的删掉。

初始值 f_{n,0,U}=1，最后答案为 f_{0,i,\emptyset}。

此时子集卷积变成差卷积，只需要取反卷积中两个集合，再正常子集卷积即可，具体可以参考代码。

复杂度也是 O(\sum_{i=1}^{n}(n-i)(i-1)^22^{i-1})。

Code

可以证明上面提到的复杂度均为 O(2^nn^2)。

常数较大，看看就好。题解中 dp 数组名字用了 H，其他都一样。

::::success[Code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=20+2,MAXS=(1<<20)+5,mod=998244353;
#define lb(x) (x&-x)
int n,m,E[MAXN][MAXN],pc[MAXS],inv[MAXN],fac[MAXN];
inline void FWT(int*A,int lim){
    for(int mid=1;mid<(1<<lim);mid<<=1){
        for(int R=mid<<1,i=0;i<(1<<lim);i+=R){
            for(int j=0;j<mid;j++)(A[i|j|mid]+=A[i|j])%=mod;
        }
    }
}
inline void IWT(int*A,int lim){
    for(int mid=1;mid<(1<<lim);mid<<=1){
        for(int R=mid<<1,i=0;i<(1<<lim);i+=R){
            for(int j=0;j<mid;j++)(A[i|j|mid]+=mod-A[i|j])%=mod;
        }
    }
}
int P[MAXN][MAXS],Q[MAXN][MAXS],R[MAXN][MAXS];
inline void Exp(int*A,int*B,int lim){
    for(int i=0;i<=lim;i++)for(int S=0;S<(1<<lim);S++)P[i][S]=Q[i][S]=0;
    for(int S=0;S<(1<<lim);S++)P[pc[S]][S]=A[S];
    for(int i=0;i<=lim;i++)FWT(P[i],lim);
    for(int S=0;S<(1<<lim);S++){
        Q[0][S]=1;
        for(int i=1;i<=lim;i++)for(int j=1;j<=i;j++){
            (Q[i][S]+=inv[i]*j%mod*P[j][S]%mod*Q[i-j][S]%mod)%=mod;
        }
    }
    for(int i=0;i<=lim;i++)IWT(Q[i],lim);
    for(int S=0;S<(1<<lim);S++)B[S]=Q[pc[S]][S];
}
int f[MAXS],tmp[MAXS],lin[MAXS];
int*H[MAXN][MAXN],vl[MAXS];
inline void juan(int*A,int*B,int*C,int lim){
    int U=(1<<lim)-1;
    for(int i=0;i<=lim;i++)for(int S=0;S<(1<<lim);S++)P[i][S]=Q[i][S]=R[i][S]=0;
    for(int S=0;S<(1<<lim);S++){
        P[pc[S]][S]=A[U^S],Q[pc[S]][S]=B[S];
    }
    for(int i=0;i<=lim;i++)FWT(P[i],lim),FWT(Q[i],lim);
    for(int S=0;S<(1<<lim);S++){
        for(int i=0;i<=lim;i++)for(int j=0;i+j<=lim;j++){
            (R[i+j][S]+=P[i][S]*Q[j][S]%mod)%=mod;
        }
    }
    for(int i=0;i<=lim;i++)IWT(R[i],lim);
    for(int S=0;S<(1<<lim);S++)C[U^S]=R[pc[S]][S];
}
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;u--,v--;
        E[u][v]++,E[v][u]++;
    }
    fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    inv[1]=1;for(int i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int S=1;S<(1<<n);S++)pc[S]=pc[S^lb(S)]+1;
    f[1]=1;
    for(int i=1;i<n;i++){
        for(int S=0;S<(1<<i);S++){
            int tim=0;
            for(int j=0;j<i;j++)if(S>>j&1){
                tim+=E[j][i];
            }
            tmp[S]=f[S]*tim%mod;
        }
        Exp(tmp,tmp,i);
        for(int S=0;S<(1<<i);S++){
            f[S|(1<<i)]=tmp[S];
        }
    }
    for(int i=0;i<=n;i++)for(int j=0;j<=n-i;j++){
        H[i][j]=new int[(1<<i)];
        for(int S=0;S<(1<<i);S++)H[i][j][S]=0;
    }
    H[n][0][(1<<n)-1]=1;
    for(int i=n-1;i>=0;i--)for(int j=0;j<=n-i;j++){
        for(int S=0;S<(1<<i);S++)vl[S]=f[S|(1<<i)];
        if(j){
            for(int S=0;S<(1<<i);S++)lin[S]=H[i+1][j-1][S|(1<<i)];
            juan(lin,vl,tmp,i);
        }else{
            for(int S=0;S<(1<<i);S++)tmp[S]=0;
        }
        for(int S=0;S<(1<<i);S++){
            H[i][j][S]=tmp[S];
            if(j!=n-i)(H[i][j][S]+=H[i+1][j][S])%=mod;
        }
    }
    for(int i=1;i<n;i++)cout<<H[0][n-i][0]*fac[i]%mod<<"\n";
}

::::