HS
AFO
HS的博客
DCOJ17 无向图计数

题目链接

DCOJ

题目描述

定义一个无向图的权值为连通块个数的 $m$ 次方。

求 $n$ 个点的所有有标号无向图的权值和,答案对 $1945555039024054273$($27\times 2^{56}+1$,是一个质数)取模。

输入格式

第一行两个非负整数 $n,m$。

输出格式

输出一行一个整数,表示答案对 $1945555039024054273$ 取模的结果。

输入输出样例

输入 #1

3 1

输出 #1

13

说明/提示

100%的数据满足 $1\leq n \leq 10^5,0\leq m \leq 15$。

详细数据范围
测试点编号 n m
1 ≤105 =0
2 =1
3~8 ≤2×103 ≤15
9~14 ≤2×104
15~20 ≤105

分析

设$F(x)$表示有标号无向图的个数,$G(x)$表示有编号无向连通图的个数。

则有
$$
F(n)=2^{\frac{n(n-1)}{2}},F(0)=1
$$

$$
F(x)=e^{G(x)}
$$

$$
G(x)=lnF(x)
$$

设$H(x)$为答案多项式。

则有
$$
H(x)=\sum_{i=0}^{\infty}i^m\frac{G^i(x)}{i!}
$$
接下来就是喜闻乐见的化式子环节。
$$
H(x)=\sum_{i=0}^{\infty}\sum_{j=0}^m\binom{i}{j}\begin{Bmatrix}m\\j\end{Bmatrix}j!\frac{G^i(x)}{i!}
$$

$$
H(x)=\sum_{j=0}^m\begin{Bmatrix}m\\j\end{Bmatrix}\sum_{i=0}^{\infty}\binom{i}{j}j!\frac{G^i(x)}{i!}
$$

$$
H(x)=\sum_{j=0}^m\begin{Bmatrix}m\\j\end{Bmatrix}\sum_{i=0}^{\infty}\frac{i!}{j!(i-j)!}j!\frac{G^i(x)}{i!}
$$

$$
H(x)=\sum_{j=0}^m\begin{Bmatrix}m\\j\end{Bmatrix}\sum_{i=0}^{\infty}\frac{G^i(x)}{(i-j)!}
$$

$$
H(x)=\sum_{j=0}^m\begin{Bmatrix}m\\j\end{Bmatrix}G^j(x)\sum_{i=0}^{\infty}\frac{G^i(x)}{i!}
$$

$$
H(x)=\sum_{j=0}^m\begin{Bmatrix}m\\j\end{Bmatrix}G^j(x)e^{G(x)}
$$

$$
H(x)=e^{G(x)}\sum_{j=0}^m\begin{Bmatrix}m\\j\end{Bmatrix}G^j(x)
$$

复杂度$O(nmlogn)$。

一些对我而言的坑

开文件…没开文件卡了评测$200s+$。

代码

#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
#define maxm 20
const long long p=1945555039024054273;
const int g=5;
const long long inv2=972777519512027137;
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...);
}
long long add(long long x,long long y)
{
    return x+y>=p? x+y-p:x+y;
}
long long sub(long long x,long long y)
{
    return x-y<0? x-y+p:x-y;
}
long long mul(long long x,long long y)
{
    return (x*y-(long long)((long double)x/p*y+1.0e-8)*p+p)%p;
}
long long fpow(long long x,long long y)
{
    long long res=1;
    while(y)
    {
        if(y&1)
            res=mul(res,x);
        x=mul(x,x);
        y>>=1;
    }
    return res;
}
Poly F,G,H;
int n,m;
long long jc[maxn],inv[maxn],ifac[maxn],Stln[maxm][maxm];
int main()
{
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    read(n,m);
    jc[0]=inv[0]=ifac[0]=1;
    jc[1]=inv[1]=ifac[1]=1;
    for(int i=2;i<=n;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(n+1);
    for(int i=1;i<=n;i++)
        F[i]=mul(ifac[i],fpow(2,1ll*i*(i-1)>>1));
    F=F.Ln();
    Stln[0][0]=1;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=i;j++)
            Stln[i][j]=add(mul(j,Stln[i-1][j]),Stln[i-1][j-1]);
    G[0]=1;
    for(int j=0;j<=m;j++,G=(F*G).split(n+1))
        H+=Stln[m][j]*G;
    printf("%lld\n",mul((H*F.Exp())[n],jc[n]));
    return 0;
}

Gluttony

文章作者

发表评论

textsms
account_circle
email

HS的博客

DCOJ17 无向图计数
生成函数+斯特林数
扫描二维码继续阅读
2020-04-22