好图计数
这道题目非常简单，它甚至没有题目背景、没有任何故事。
但为了能让你顺利理解题目，善良的 Yazid 将为你介绍一些概念。
-
简单图：不存在重边、自环的图。（重边即为两条完全相同的边，自环即为两端点为同一节点的边）
-
补图：一个图 (G) 的补图有与 (G) 完全相同的节点，且任意两点之间有边当且仅当他们在 (G) 中不相邻。
我们归纳定义一个无向简单图是好的：
-
一个单点是好的。
-
若干个好的图分别作为联通块所形成的图是好的。
-
一个好的图的补图是好的。
给定一个正整数 (n)。
求 (n) 个点的本质不同的好的图的数量对质数 (P) 取模的结果。（这里的 (P) 是一个常数，具体见【输入格式】）
两个好的图的被认为是本质不同的，当且仅当无论如何将一个图重标号，它都不能与另一个图完全相同。
保证 (Tleq 233)，(nleq 23333)，(2^{29} < P < 2^{30}) 且保证 (P) 为质数。
题解
https://jklover.hs-blog.cf/2020/07/19/Loj-6389-好图计数/#more
生成函数+欧拉变换。
好图肯定是由若干个完全图组合起来的。
对于一张连通的图,若它的补图也是连通图,根据定义,当 (n>1) 时,它们都不是好图.而不连通的图的补图一定是连通的,于是可以得出,当 (n>1) 时,连通好图和不连通好图是可以用补图关系一一对应的,两者数目相等.
设 (f_i) 表示 (i) 个点的好图的数目, (g_i) 表示 (i) 个点连通好图的数目,则有 (f_0=f_1=g_1=1,f_i=2cdot g_i(i>1)) .
考虑 (f_i) 的生成函数 (F(x)) ,枚举大小为 (k) 的连通块数目,在无标号下可以得出
依次枚举 (n) ,过程中暴力维护每个 (sum g_kcdot k) ,时间复杂度 (O(n^2)) .
需要老生常谈的取模优化才能通过这题。
CO int N=23333+1;
CO int64 inf=4e18;
int inv[N];
int f[N],g[N],h[N];
void update(int k){
int val=mul(k,g[k]);
for(int i=k;i<N;i+=k) inc(h[i],val);
}
int main(){
int T=read<int>();read(mod);
f[0]=f[1]=g[1]=inv[1]=1;
update(1);
for(int n=1;n<N-1;++n){
int64 sum=0;
for(int i=0;i<=n;++i){
sum+=(int64)f[i]*h[n-i+1];
if(sum>inf) sum%=mod;
}
inv[n+1]=mul(mod-mod/(n+1),inv[mod%(n+1)]);
g[n+1]=mul(sum%mod,inv[n+1]);
f[n+1]=add(g[n+1],g[n+1]);
update(n+1);
}
while(T--) printf("%d
",f[read<int>()]);
return 0;
}