Luogu5448 [THUPC2018] 好图计数

题意：我们归纳定义一个无向简单图是好的：

• 一个单点是好的。

• 若干个好的图分别作为联通块所形成的图是好的。

• 一个好的图的补图是好的。

求 个点的无标号好图的数量，答案对给定质数 取模。

，，时限 。

---

设 为好图， 为联通好图。则显然有 。

能够发现，如果一个不连通的好图取补图，一定能得到一个联通好图，反之亦然，这是双射。

这只在一个地方不成立， 时一个点的补图是自己。

那么，。 钦定 。

写出生成函数形式并变形 :

• 设 ，有 。

  在得知 之后可以枚举倍数 （一边递推一边并行）计算。

则有 提取 系数可得 注意 ，实际上不需要牵涉到 ，但是会牵涉到 故 边界为 。

暴力递推，复杂度 ，卡常后可以通过。