「THUPC2018」好图计数 / Count （生成函数）（组合数学）

本文主要是介绍「THUPC2018」好图计数 / Count （生成函数）（组合数学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

首先有 “不连通图的补图一定联通”
所以不连通的好图的补图一定是联通好图
而若一个图是联通图且补图为联通图，那么根据定义这个图不是好图
于是发现联通好图的个数 = 不连通好图个数

设不连通好图或者是联通好图的个数为 $g_i$，好图个数为 $f_i$，那么有 $f_i=2\ast g_i$
考虑 $f_i$ 的生成函数 $F(x)$
一个好图是由若干个联通好图拼接而成的，这里是无标号，所以是集合内无标号集合间无序拼接
枚举一种大小的图的个数及种类可以得
$$F=\prod _{k\ge 1}(1-x^k{)}^{-g_k}$$
两边取 $ln$ 再求导得
$$\frac{F^{\prime }}{F}=\sum _{k\ge 1}{g}_k\frac{k\ast x^{k-1}}{1-x^k}$$
考虑第 $n$ 项的系数
$$(n+1)f_{n+1}=\sum _{i=0}^n{f}_i\ast [x^{n-i}]\sum _{k\ge 1}{g}_k\frac{k\ast x^{k-1}}{1-x^k}$$
考虑这样一个东西
$[x^n]{\sum }_{k\ge 1}{g}_k\frac{k\ast x^{k-1}}{1-x^k}$，$\frac{x^{k-1}}{1-x^k}$只在 $x^{ik-1}(i\ge 1)$ 有值
所以$[x^n]{\sum }_{k\ge 1}{g}_k\frac{k\ast x^{k-1}}{1-x^k}={\sum }_{k|n+1}k\ast g_k$
所以
$$(n+1)f_{n+1}=\sum _{i=0}^n{f}_i\sum _{k|n-i+1}k\ast g_k$$
$i=0$ 的时候需要移一下项，可以得到
$$\frac{n+1}{2}{f}_{n+1}=\sum _{i=1}^n{f}_i\sum _{j|n-i+1}j\ast g_j+\sum _{j|n+1,j\ne n+1}j\ast g_j$$
维护一下后面一坨，调和级数更新，前面暴力递推，小常数 $O(n^2)$ 卡过

Upd 20/09/04：
重新做了一遍，感觉之前做得很蠢
建立联通好图和不连通关系，容易列出如下式子
$2F(z)=\mathcal{E}(F(z))+1-z$
这个直接牛顿迭代就可以了

#include<bits/stdc++.h>
#define cs const
using namespace std;
cs int N = 23333;
typedef long long ll;
int read(){int cnt = 0, f = 1; char ch = 0;while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; }while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();return cnt * f;
}
int Mod;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int mul(int a, int b){ ll r=(ll)a*b; if(r>=Mod) r%=Mod; return r; }
int ksm(int a, int b){ int ans=1; for(;b;b>>=1,a=mul(a,a)) if(b&1) ans=mul(ans,a); return ans; }
int T, n, f[N+5], g[N+5], s[N+5];
int main(){T = read(); Mod = read();f[0] = f[1] = 1;for(int i = 1; i <= N; i++) s[i] = 1;for(int i = 1; i < N; i++){ll tmp = 0;for(int j = 0; j <= i; j++){tmp += (ll)f[j]*s[i+1-j];if(tmp>7e18) tmp%=Mod;} tmp %= Mod; g[i+1] = mul(tmp,ksm(i+1,Mod-2));f[i+1] = add(g[i+1],g[i+1]);for(int j=i+1; j<=N; j+=i+1) s[j]=add(s[j],tmp);}while(T--) cout << f[read()] << '\n';return 0;
}

这篇关于「THUPC2018」好图计数 / Count （生成函数）（组合数学）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---