自动搬运

查看原文

来自洛谷，原作者为

	b2019dy **

搬运于2025-08-24 22:10:52，当前版本为作者最后更新于2019-08-13 20:29:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

这个结论是怎么来的呢

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

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

我们设$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]);
	}
}