题解：P14270 ABC253Ex 加强版

· · 题解

设 h_i 表示有 i 个极大连通块的无向无环图数量。

则 ans_i=\frac{i!h_{n-i}}{m^i}，这下只需要计数 h_i。

声明：以下指的集合幂级数运算均为无交并。

设 g_S 表示只考虑 S 内点及其导出子图，保留边使得最后是棵树的方案数。

逐点牛顿迭代。

具体地，我们考虑先得出 (\max_{i\in S}i)< x 的 S 的方案，再推到 x 上，重复 n 次。

首先显然 x\notin S 的 g_S，直接继承过去就好。

我们再搞一个新的集幂 f_S=E(\{i\},S)g_S，然后对之 \exp，再把 i 拼回去转移到 g 上。

这个复杂度是 O(\sum\limits_{i=1}^n2^ii^2)=O(2^nn^2)。可以通过。

现在考虑求出 h_i=[x^U]g^i，可以直接暴力子集卷积，然后白干。

能过 n\le 14，但过不去 n\le 20。

考虑 dp_{i,S} 表示已经加入了 i 个连通块，其点集为 S。

我们每次加入还没被 S 包含的编号最小的节点所在的连通块。

这样有什么好处呢？

首先不会算重，因为一种方案加入的顺序是唯一的。

然后我们还可以发现 \{1,\dots ,i\}\subseteq S。

我们考虑 dp_i 怎么转移到 dp_{i+1}？直接跟 g 子集卷积就行。

这个过程你发现前 i 位一定不会用到，因为肯定都在 S 里出现过。

所以做一个大小为 n-i 的子集卷积就行了。

也是 O(2^nn^2)，于是做完……了吗？

发现还有一个问题，就是很难钦定每次加入最小的连通块。

这是好办的，你按 S 中最小的元素将 S 分组，对每一组跑子集卷积。

你发现复杂度还是对的。

这部分的代码：

#include<bits/stdc++.h>
#define ppc(x) __builtin_popcount(x)

using namespace std;

namespace Fread {
    const int SIZE=1<<21;char buf[SIZE],*S,*T;
    inline char getchar() {if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return '\n';}return *S++;}
}
namespace Fwrite {
    const int SIZE=1<<21;
    char buf[SIZE],*S=buf,*T=buf+SIZE;
    inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}
    inline void putchar(char c){*S++=c;if(S==T)flush();}
    struct POPOSSIBLE{~POPOSSIBLE(){flush();}}ztr;
}
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
namespace Fastio{
    struct Reader{
        template<typename T>
        Reader& operator >> (T& x) {
            char c=getchar();T f=1;
            while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}x=0;
            while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}x*=f;
            return *this;
        }
        Reader(){}
    }cin;
    struct Writer{
        template<typename T>
        Writer& operator << (T x) {
            if(x==0){putchar('0');return *this;}
            if(x<0){putchar('-');x=-x;}
            static int sta[45];int top=0;
            while(x){sta[++top]=x%10;x/=10;}
            while(top){putchar(sta[top]+'0');--top;}
            return *this;
        }
        Writer& operator << (char c) {putchar(c);return *this;}
        Writer(){}
    }cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout

const int N=31,Max=1048577,mod=998244353;
struct modint {
    int val;
    static int norm(const int& x) { return x < 0 ? x + mod : x; }
    inline int Mod(int x){return x>=mod?x-mod:x;}
    modint inv() const {
        int a = val, b = mod, u = 1, v = 0, t;
        while (b > 0) t = a / b, swap(a -= t * b, b), swap(u -= t * v, v);
        return modint(u);
    }
    modint() : val(0) {}
    modint(const int& m) : val(norm(m)) {}
    modint(const long long& m) : val(norm(m % mod)) {}
    modint operator-() const { return modint(norm(-val)); }
    modint& operator+=(const modint& o) { return val = Mod(val + o.val), *this; }
    modint& operator-=(const modint& o) { return val = norm(1ll * val - o.val), *this; }
    modint& operator*=(const modint& o) { return val = static_cast<int>(1ll * val * o.val % mod), *this; }
    modint operator-(const modint& o) const { return modint(*this) -= o; }
    modint operator+(const modint& o) const { return modint(*this) += o; }
    modint operator*(const modint& o) const { return modint(*this) *= o; }
    friend std::ostream& operator<<(std::ostream& os, const modint& a) { return os << a.val; }
    friend Fastio::Writer& operator<<(Fastio::Writer& os, const modint& a) { return os << a.val; }
}frac[N],inv[N],pw[Max],h[N];

int n,m,pre[Max],fg[N][N];

inline void init(int n=30){
    frac[0]=inv[0]=1;for(int i=1;i<=n;++i) frac[i]=frac[i-1]*i;
    inv[n]=frac[n].inv();for(int i=n-1;i;--i) inv[i]=inv[i+1]*(i+1);
}
inline modint Inv(int x){return frac[x-1]*inv[x];}

struct QAQ{QAQ(){init();}}QAQ;
struct poly{
    vector<modint> p;modint& operator [](int x){return p[x];}
    inline void init(int n){p.clear();p.resize(1<<n);}
    inline void emplace(int n){p.resize(1<<n);}
    inline int deg(){return p.size();}
    inline void FMT(){int len=p.size(),n=__lg(len);for(int i=0;i<n;++i) for(int j=0;j<1<<n;++j) if((j>>i)&1) p[j]+=p[j^(1<<i)];}
    inline void IFMT(){int len=p.size(),n=__lg(len);for(int i=0;i<n;++i) for(int j=0;j<1<<n;++j) if((j>>i)&1) p[j]-=p[j^(1<<i)];}
}x,f,g,y,dp[21];
inline int except(int S,int x){return ((S>>(x+1)<<x)|(S&((1<<x)-1)));}
inline void Mul(poly x,poly y,poly &z){//x*y->z
    x.FMT();y.FMT();int len=x.deg();
    z.p.resize(len);if(y.deg()!=len) exit(-1);
    for(int i=0;i<len;++i) z[i]=x[i]*y[i];
    z.IFMT();
}
poly ln(poly x){
    static poly f[N],g[N];int n=__lg(x.deg());
    for(int i=0;i<=n;++i){f[i].init(n);g[i].init(n);}
    for(int i=0;i<(1<<n);++i) f[ppc(i)][i]=x[i];
    for(int i=0;i<=n;++i) f[i].FMT();
    for(int i=0;i<1<<n;++i){
        g[0][i]=0;
        for(int j=1;j<=n;++j){
            for(int k=1;k<j;++k) g[j][i]-=f[k][i]*g[j-k][i]*(j-k);
            g[j][i]=f[j][i]+g[j][i]*Inv(j);
        }
    }
    for(int i=0;i<=n;++i) g[i].IFMT();
    for(int i=0;i<1<<n;++i) x[i]=g[ppc(i)][i];
    return x;
}
poly exp(poly x){
    static poly f[N],g[N];int n=__lg(x.deg());
    for(int i=0;i<=n;++i){f[i].init(n);g[i].init(n);}
    for(int i=0;i<(1<<n);++i) f[ppc(i)][i]=x[i];
    for(int i=0;i<=n;++i) f[i].FMT();
    for(int i=0;i<(1<<n);++i){
        g[0][i]=1;
        for(int j=1;j<=n;++j){
            for(int k=1;k<=j;++k) g[j][i]+=f[k][i]*k*g[j-k][i];
            g[j][i]*=Inv(j);
        }
    }
    for(int i=0;i<=n;++i) g[i].IFMT();
    for(int i=0;i<1<<n;++i) x[i]=g[ppc(i)][i];
    return x; 
}
poly submul(poly x,poly &y){
    static poly f[N],g[N],h[N];int n=__lg(x.deg());
    for(int i=0;i<=n;++i){f[i].init(n);g[i].init(n);h[i].init(n);}
    for(int i=0;i<(1<<n);++i) f[ppc(i)][i]=x[i];
    for(int i=0;i<(1<<n);++i) g[ppc(i)][i]=y[i];
    for(int i=0;i<=n;++i) f[i].FMT(),g[i].FMT();
    for(int i=0;i<1<<n;++i){
        for(int j=0;j<=n;++j){
            for(int k=0;k<=j;++k) h[j][i]+=f[k][i]*g[j-k][i];
        }
    }
    for(int i=0;i<=n;++i) h[i].IFMT();
    for(int i=0;i<1<<n;++i) x[i]=h[ppc(i)][i];
    return x;
}
inline poly Mul(poly &x,poly &y){poly z;Mul(x,y,z);return z;}
inline int E(int S,int T){return pre[S+T]-pre[S]-pre[T];}
inline int P(int i,int T){return E((1<<i),T);}
inline modint expow(modint x,int y){modint res=1;for(;y;y>>=1,x*=x) if(y&1) res*=x;return res;}

int main(){
    cin>>n>>m;for(int i=1,x,y;i<=m;++i){cin>>x>>y;--x;--y;++pre[(1<<x)|(1<<y)];}
    for(int i=0;i<n;++i) for(int j=0;j<(1<<n);++j) if((j>>i)&1) pre[j]+=pre[j^(1<<i)];
    g.init(1);g[1]=1;
    for(int i=1;i<n;++i){
        f.init(i);g.emplace((i+1));
        for(int j=0;j<(1<<i);++j) f[j]=g[j]*P(i,j);
        f=exp(f);for(int j=0;j<(1<<i);++j) g[(1<<i)|j]=f[j];
    }
    dp[1]=g;h[1]=dp[1][(1<<n)-1];
    for(int i=0;i<(1<<n);++i) if(!(i&1)) dp[1][i]=0;
    for(int i=2;i<=n;++i) dp[i].init(n);
    for(int i=1;i<n-1;++i){
        for(int j=i;j<n;++j){
            x.init(n-j);for(int k=0;k<(1<<(n-j));++k) if(!(k&1)) x[k]=dp[i][(k<<j)+(1<<j)-1];
            y.init(n-j);for(int k=0;k<(1<<(n-j));++k) if((k&1)) y[k]=g[k<<j];
            x=submul(x,y);for(int k=0;k<(1<<(n-j));++k) if((k&1)) dp[i+1][(k<<j)+(1<<j)-1]+=x[k];
        }
        h[i+1]=dp[i+1][(1<<n)-1];
    }
    for(int i=1;i<n;++i){
        cout << frac[i]*h[n-i] << '\n';
    }
    return 0;
}