图计数

无向连通图计数

总方案数 $g_{n} = 2^{(2 n)}$ ，减去不连通的方案数，枚举 $1$ 所在连通块的大小。

$f_{n} = g_{n} - \sum_{i = 1}^{n - 1} (i - 1 n - 1) f_{i} g_{n - i}$

加强版 P4841，分治 ntt 加速。

int n;
int f[maxn],g[maxn];
int fac[maxn],inv[maxn];
using ploy::mul;
void sovle(int l,int r){
	if(l==r){
		f[l]=(g[l]+mod-f[l]*fac[l-1]%mod)%mod;
		return ;
	}
	int mid=l+r>>1;
	sovle(l,mid);
	vector<int> p(mid-l+1),q(r-l+1);
	for(int i=l;i<=mid;i++)p[i-l]=f[i]*inv[i-1]%mod;
	for(int i=1;i<=r-l;i++)q[i]=g[i]*inv[i]%mod;
	vector<int> ans=mul(p,q);
	for(int i=mid+1;i<=r;i++)inc(f[i],ans[i-l]);
	sovle(mid+1,r);
}
void work(){
	n=read();
	fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	inv[n]=ksm(fac[n]);for(int i=n-1;~i;i--)inv[i]=inv[i+1]*(i+1)%mod;
	for(int i=1;i<=n;i++)g[i]=ksm(2,i*(i-1)/2);
	sovle(1,n);
	printf("%lld\n",f[n]);
}

abc236h

钦定若干组组内相等，方案为 $\frac{m}{l c m ( d _{i} )}$ 。状压，枚举包含 $m n_{S}$ 的子集乘方案数和容斥系数转移。

对于 $(2 n)$ 个不等关系钦定 $i$ 个相等相等的容斥系数为 $(- 1)^{i}$ 。钦定组内相等的容斥系数为构成大小为 $s i z$ 无向连通图的选边方案的容斥系数之和。

$n$ 个点乱连的系数为 $\sum_{i = 0}^{\frac{n ( n - 1 )}{2}} (i \frac{n ( n - 1 )}{2}) (- 1)^{i} = [\frac{n ( n - 1 )}{2} = 0] = [n = 1]$ 。减去不连通图的贡献， $n$ 个点的无向连通图的容斥系数和为 $f_{n} = [n = 1] - \sum_{i = 1}^{n - 1} C (n - 1, i - 1) f_{i} [n - i == 1]$ 。

欧拉图计数

要求偶度数且连通。偶度数图的数量 $g_{n} = 2^{(2 n - 1)}$ ， $1, \dots, n - 1$ 乱连， $n$ 调整。连通的计数同无向连通图计数。

DAG计数

钦定入度为 $0$ 的点数，分配容斥系数使得 $\sum_{T \subseteq S} f (T) = 1$ 。

$f_{n} = \sum_{i = 1}^{n} (- 1)^{i + 1} (i n) 2^{i (n - i)} f_{n - i}$

P10221

设 $f_{i, s}$ 表示 $s$ 分为 $i$ 个非空段形成 DAG 的方案， $g_{i, s}$ 为 $s$ 分为 $i$ 个非空段段间没有边的方案数。容斥系数同 DAG 计数，可以做到 $O (3^{n} n^{2})$ 。设 $F_{S} (x) = \sum f_{i, S} x^{i}$ ， $F_{S} (x) = G_{T} (x) F_{S \oplus T} (x)$ ，拉插之后算系数，复杂度 $O (3^{n} n)$ 。

perfur 序列

$n$ 个点的数和长为 $n - 2$ 值域 $[1, n]$ 的序列的双射。取出编号最小的叶子结点删去，将其父亲加到序列末端。

n 个点有标号无根树数量 $n^{n - 2}$ 。确定度数之后 $\frac{( n - 2 )!}{\prod ( d _{u} - 1 )!}$ 。已经形成 $k$ 个连通块后 $(\sum s_{i})^{k - 2} \prod s_{i}$ 。

P6596

设 $d p_{i, j}$ 为 $i$ 个点 $j$ 条割边的 $j + 1$ 个边双的大小之积。 $d p_{i, j} = \sum_{k} (k i) d p_{i - k, j - 1} d p_{k, 0}$ 。 $j + 1$ 个点双没有顺序，再除掉 $\frac{1}{( j + 1 )!}$ 。 $d p_{i, 0}$ 为大小为 $i$ 的无向连通图数量减去 $j > 0$ 的 $d p_{i, j}$ 再乘 $i$ 。答案为 $\sum d p_{n, i} n^{i - 1}$ 。

🪴 Quartz 4.0

Explorer

图计数