Wuyanru's blog
0%

[QOJ10523] 最小生成树

发表于 分类于 ，

哇酷哇酷的简单多项式题。

题目链接。

题意

给定 ，求有多少 个点的简单无向连通图满足以下条件，模数为 ：

  1. 图中所有边的边权为 中的整数；
  2. 对于图中每一条边，都有至少一个最小生成树包含它。

，。

题解

首先考虑怎么样的一张图是合法的。

考虑从小到大加入边，并像 Kruskal 一样合并连通块。

当加入完所有权值为 的边的时候，整个图存在若干个连通块，此时所有权值为 的边两端不能处于一个连通块。

若所有边都满足这个条件，并且整个图是连通的，那么这张图就是满足条件的。

考虑设 表示只使用 种边权，将 个点连成一个连通块的方案数； 表示只使用 种边权，将 个点连成若干连通块方案数。

显然，边界条件为 和 。

先来考虑 怎么转移，考虑用 减去至少有两个连通块的情况。

那么直接枚举第一个点所在连通块的大小即可，有 。

这个东西容易使用分治 NTT 在 复杂度内维护。

再来考虑 的转移，考虑前 种边权的边加进去之后，整张图构成了哪些连通块。

假设此时有 个连通块，大小分别为 ，并且 ，那么此时方案数为 。

不难发现，方案数相当于 。

那么设 和 。

那么可以发现 。

这里和上面一样，可以用分治 NTT。

时间复杂度 ，似乎可以用多项式 exp 之类的少一个 ，但我不会，难过。

update：我好像会了，开心。

考虑一个多项式 ，我们要求出 。

求导，得 。

分离 系数，得 。

即 即 。

而上面的 等价于 。

这两个几乎一样，所以我们只需要凑一凑 的系数就可以用多项式 exp 来 完成这个玩意了。

代码

双老哥随便草。

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int mod=998244353;
const int G=3;
const int NG=(mod+1)/G;
int wh[131072];
ll f[131072];
ll g[131072];
inline ll qow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
inline void NTT(ll *f,int L,bool dft)
{
    for(int i=0;i<(1<<L);i++) if(i<wh[i]) swap(f[i],f[wh[i]]);
    for(int len=0;len<L;len++)
    {
        ll step=qow(dft?G:NG,(mod+1)>>(len+1));
        for(int l=0,r=2<<len;l<(1<<L);l=r,r+=2<<len)
        {
            ll now=1;
            for(int i=l,j=l+(1<<len);j<r;i++,j++)
            {
                ll num=f[j]*now%mod;
                f[j]=(f[i]-num+mod)%mod;
                f[i]=(f[i]+num)%mod;
                now=now*step%mod;
            }
        }
    }
    if(!dft)
    {
        ll num=qow(1<<L,mod-2);
        for(int i=0;i<(1<<L);i++) f[i]=f[i]*num%mod;
    }
}
inline void NTT(int L)
{
    for(int i=0;i<(1<<L);i++) wh[i]=(wh[i>>1]>>1)|((i&1)?(1<<(L-1)):0);
    NTT(f,L,1),NTT(g,L,1);
    for(int i=0;i<(1<<L);i++) f[i]=f[i]*g[i]%mod;
    NTT(f,L,0);
}

ll jc[50005],inv[50005];
ll p2[50005],ip2[50005];
ll dp[11][50005];
ll fp[11][50005];
int n,k;
inline ll C(int a,int b)
{
    if(a<b||b<0) return 0;
    return jc[a]*inv[b]%mod*inv[a-b]%mod;
}
inline void cdq_fp(int k,int l,int r)
{
    if(l==r)
    {
        fp[k][l]=(dp[k-1][l]+fp[k][l]*p2[l])%mod;
        return ;
    }
    int mid=(l+r)>>1;
    cdq_fp(k,l,mid);

    int llen=mid-l+1,rlen=r-l,alen=llen+rlen,L=0;
    while((1<<L)<alen) L++;
    memset(f,0,sizeof(ll)<<L);
    memset(g,0,sizeof(ll)<<L);
    for(int i=l;i<=mid;i++) f[i-l]=fp[k][i]*ip2[i]%mod*inv[i]%mod;
    for(int i=1;i<=r-l;i++) g[i-1]=dp[k-1][i]*ip2[i]%mod*inv[i-1]%mod;
    NTT(L);// f[mid-l] -> fp[mid+1]
    for(int i=mid+1;i<=r;i++) (fp[k][i]+=jc[i-1]*f[i-1-l])%=mod;

    cdq_fp(k,mid+1,r);
}
inline void cdq_dp(int k,int l,int r)
{
    if(l==r)
    {
        dp[k][l]=(fp[k][l]-dp[k][l]+mod)%mod;
        return ;
    }
    int mid=(l+r)>>1;
    cdq_dp(k,l,mid);

    int llen=mid-l+1,rlen=r-l,alen=llen+rlen,L=0;
    while((1<<L)<alen) L++;
    memset(f,0,sizeof(ll)<<L);
    memset(g,0,sizeof(ll)<<L);
    for(int i=l;i<=mid;i++) f[i-l]=dp[k][i]*inv[i-1]%mod;
    for(int i=1;i<=r-l;i++) g[i-1]=fp[k][i]*inv[i]%mod;
    NTT(L);// f[mid-l] -> dp[mid+1]
    for(int i=mid+1;i<=r;i++) (dp[k][i]+=jc[i-1]*f[i-1-l])%=mod;

    cdq_dp(k,mid+1,r);
}
int main()
{
    n=read(),k=read();
    dp[0][1]=jc[0]=inv[0]=p2[0]=ip2[0]=1;
    for(int i=1;i<=n;i++)
    {
        fp[0][i]=1;
        jc[i]=jc[i-1]*i%mod;
        inv[i]=qow(jc[i],mod-2);
        p2[i]=p2[i-1]*qow(2,i-1)%mod;
        ip2[i]=qow(p2[i],mod-2);
    }
    for(int i=1;i<=k;i++) cdq_fp(i,1,n),cdq_dp(i,1,n);
    printf("%lld\n",dp[k][n]);
    return 0;
}