HS
AFO
HS的博客
LOJ6363「地底蔷薇」

题目链接

LOJ

题目描述

由于内部原因,题目背景没了。

给定集合 $S$ ,请你求出 $n$ 个点的「所有极大点双连通分量的大小都在 $S$ 内」的不同简单无向连通图的个数对 $998244353$ 取模的结果。

点双连通分量:删去任意一个点后剩下的点依然保持连通的连通子图。
极大点双连通分量:一个点双连通分量,且不存在更大的点双连通分量包含自己。
极大点双连通分量的大小:指连通分量包含的点数。
两个简单无向图不同,当且仅当存在某条边 $(u,v)$ 出现在了其中一个无向图,而没有出现在另一个无向图。

输入格式

第一行包含两个整数 $n,|S|$ ,表示图的点数以及集合 $S$ 的大小。
第二行包含 $|S|$ 个整数,表示集合 $S$ 的元素。

输出格式

包含一个整数,表示答案对 $998244353$ 取模的结果。

输入输出样例

输入 #1

5 1
2

输出 #1

125

说明/提示

$S={2}$,可以证明这等价于图中不存在环。$5$ 个点的有标号无根树共有 $5^3=125$ 种。

分析

首先设$F(x)$为有根无向连通图的个数,$G(x)$为有标号点双连通图的个数。

考虑对于根,删除原本和它在一个点双中的点与它之间的边,剩下的每一个原本和它在一个点双中的点都会作为一张新的有根无向连通子图的根,方案数也就是$F(x)$。

那么枚举有$i$个点是原本和它在一个点双中的点,它们的贡献就是$\sum_i \frac{g_i}{i!}F^i(x)$。

发现这个函数实际上是一个复合函数,是$G(x)$和$F(x)$复合而成的。

由于一个根结点可能在多个点双中,所以最后的贡献是$e^{G(F(x))}$。

那么也就是说有如下式子成立。
$$
F(x)=xe^{G(F(x))}
$$

移一下项。
$$
\frac{F(x)}{e^{G(F(x))}}=x
$$
发现这个式子很像复合逆。
$$
F^{-1}(x)=\frac{x}{e^{G(x)}}
$$
$F^{-1}(x)$表示$F(x)$的复合逆。

那么再移一下项。
$$
e^{G(x)}=\frac{x}{F^{-1}(x)}
$$

$$
G(x)=ln\frac{x}{F^{-1}(x)}
$$

发现右边的其实也是一个复合函数,是由$F^{-1}(x)$和$H(x)$复合而成的,其中$H(x)=ln\frac{F(x)}{x}$。

写出来就是这样。
$$
G(x)=H(F^{-1}(x))
$$
发现右边这个就是拓展拉格朗日反演的形式。

于是反演一波。
$$
[x^n]G(x)=\frac{1}{n}[x^{n-1}]H'(x)\left(\frac{x}{F(x)}\right)^{n}
$$
也就是说,我们可以在$O(nlogn)$的时间内求出$G(x)$的第$n$项。

而题目保证说求的项之和$m \le 10^5$,所以可以在$O(mlogm)$的时间内求出所有需要的值。

那么我们构造一个新的多项式,这个多项式中只有在$S$集合中的项系数不为$0$,即
$$
G'(x)=\sum_{i \in S}\frac{g_i}{i!}x^i
$$
套用之间$F(x)$与$G(x)$的关系,设答案多项式为$P(x)$。
$$
P(x)=xe^{G'(P(x))}
$$
那么可以和之前一样,得到如下式子
$$
P^{-1}(x)=\frac{x}{e^{G'(x)}}
$$
那么根据拉格朗日反演,有:
$$
[x^n]P(x)=\frac{1}{n}[x^{n-1}]\left(\frac{x}{P^{-1}(x)}\right)^{n}
$$

$$
[x^n]P(x)=\frac{1}{n}[x^{n-1}]\left(\frac{x}{\frac{x}{e^{G'(x)}}}\right)^{n}
$$

$$
[x^n]P(x)=\frac{1}{n}[x^{n-1}]e^{nG'(x)}
$$

最后由于是指数型生成函数,所以还要乘$n!$,由于算的是无根简单无向连通图,所以还要除$n$。

一些对我而言的坑

输入的元素用这个方法需要$-1$。
预处理的时候多预处理两项,因为要左移一项,还要求导。

代码

#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
const int p=998244353;
const int g=3;
const int inv2=499122177;
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
    read(b...);
}
int n,m,mx,jc[maxn<<2],inv[maxn<<2],ifac[maxn<<2];
vector<int>v;
int add(int x,int y)
{
    return x+y>=p? x+y-p:x+y;
}
int sub(int x,int y)
{
    return x-y<0? x-y+p:x-y;
}
int mul(int x,int y)
{
    return 1ll*x*y%p;
}
int fpow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1)
            res=mul(res,x);
        x=mul(x,x);
        y>>=1;
    }
    return res;
}
Poly F,G,H;
int main()
{
    read(n,m);
    for(int i=1;i<=m;i++)
    {
        int x;
        read(x);
        v.push_back(x);
        mx=max(mx,x);
    }
    jc[0]=inv[0]=ifac[0]=1;
    jc[1]=inv[1]=ifac[1]=1;
    for(int i=2;i<mx<<2;i++)
    {
        jc[i]=mul(jc[i-1],i);
        inv[i]=mul(p-p/i,inv[p%i]);
        ifac[i]=mul(ifac[i-1],inv[i]);
    }
    F[0]=1;
    F.resize(mx+1);
    for(int i=1;i<=mx;i++)
        F[i]=mul(ifac[i],fpow(2,(1ll*i*(i-1)>>1)%(p-1)));
    F=F.Ln();
    for(int i=1;i<=mx;i++)
        F[i-1]=mul(F[i],i);
    H=(F.Ln()).Deriv();
    F=F.Inv();
    G.resize(n+1);
    for(auto x:v)
        G[x-1]=mul(inv[x-1],(H.split(x-1)*((F.split(x-1)).Pow(x-1)))[x-2]);
    printf("%d\n",mul(mul((G*n).Exp()[n-1],inv[n]),jc[n-1]));
    return 0;
}

Gluttony

文章作者

发表评论

textsms
account_circle
email

HS的博客

LOJ6363「地底蔷薇」
点双连通图计数套路+拉格朗日反演
扫描二维码继续阅读
2020-04-11