题解 P5448 【[THUPC2018]好图计数】

· · 题解

我们可以得出一个结论，联通好图的不图只会是非联通好图，非联通好图的不图只会是联通好图

这个结论是怎么来的呢

若干个好图作为联通块形成的好图显然是非联通好图，也就是我们没有不通过补图构成联通好图的手段，所以联通好图的补图不可能是联通好图

而非联通好图的补图一定为联通好图，这是显然的

我们设f_n表示n个点好图数量，g_n表示n个点联通好图数量

f_n=2*g_n

我们可以先拿到这样一个结论

EGF貌似没有办法搞，我们考虑从实际意义出发来写出他的生成函数

F(x)=\prod_{k>0}(\sum_{i>0} x^{ik})^{g_k} F(x)=\prod_{k>0}(1-x^k)^{-g_k}

什么意思呢，我们考虑将若干个联通好图拼在一起

我们需要现在点数中选择一种，然后需要在点数为k的联通好图中选择一种形状，然后再选择该形状的联通好图数量，点数就是ik，为什么不用乘以2呢，因为联通好图也可以看作是一个好图拼起来的，所以他同时包含了联通好图与非联通好图的所有情况

我们难以求出累乘，于是我们对两边求ln

\ln(F(x))=-\sum g_k \ln(1-x^k)

再求个导

\frac{F'(x)}{F(x)}=\sum g_k\frac{kx^{k-1}}{1-x^k} F'(x)=F(x)\sum g_k\frac{kx^{k-1}}{1-x^k} (n+1)f(n+1)=\sum_{i=0}^n f(i)[x^{n-i}]\sum kg_k\frac{x^{k-1}}{1-x^k}

因为

\frac{x^{k-1}}{1-x^k}=\sum_{i=1}x^{ik-1}

所以上面式子仅当 k|(n+1)时有值

(n+1)f(n+1)=\sum_{i=0}^n f(i)\sum_{k|(n-i+1)}kg_k

我们把n+1，换成n

nf(n)=\sum_{i=0}^{n-1} f(i)\sum_{k|(n-i)}kg_k

这个式子就可以进行暴力递推了，我们就可以进行n^2做法

然后卡卡常就能过了

当然这个式子可以写成自卷积形式，写成自卷积形式后就可以O(nlogn^2)

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
int t,p,n;
long long f[50005],g[50005],sum[50005];
long long ksm(long long x,int n)
{
    long long ans=1;
    while(n)
    {
        if(n&1) ans=ans*x%p;
        x=x*x%p;
        n>>=1;
    }
    return ans;
}
int main()
{
    scanf("%d%d",&t,&p);
    f[0]=f[1]=1,g[1]=1;
    f[2]=2,g[2]=1;
    for(int i=1;i<=23333;i++) sum[i]=1;
    for(int i=2;i<=23333;i+=2) sum[i]+=2;
    for(long long i=3;i<=23333;i++)
    {
        __int128 tmp=0;
        for(int j=0;j<i;j++) tmp+=f[j]*sum[i-j];
        tmp%=p;
        g[i]=tmp*ksm(i,p-2)%p;
        f[i]=g[i]*2%p;
        for(int j=i;j<=23333;j+=i) sum[j]+=tmp,sum[j]%=p;
    }
    while(t--)
    {
        scanf("%d",&n);
        printf("%lld\n",f[n]);
    }
}