数数题。(雾

有标号图计数的一般方法

通用DP方程
若已知n个点满足某性质的P的图的答案为
那么求n个点的联通图满足该性质的答案为
则有
下面的描述中我们称其为成套方法。(雾

1.有标号联通图计数

第一次采取成套方法。

2.有标号欧拉图计数

还是采取成套方法,我们考虑欧拉图的本质是度数为均为偶数的连通图。
求度数为均为偶数的图,即一个点的图的个数,可以考虑每一个点按度数是否与连边。
此时有

再次利用成套方法即可。

3.有标号的二分图计数

先考虑连通的二分图计数
考虑成套方法,我们考虑二分图的本质是。

4.加速?

对形如的递推式加速。
考慮後面減去了一個卷積。
考慮到存在依賴關係。
不妨考慮cdq+fft
優化後的複雜度是$O(nlog^2n)$。
「更加优秀的加速」:
考虑$$F(n)=S(n)-\sum _ {i=1}^{n-1} \binom{n-1}{i-1} F(i)S(n-i)$$
即$$S(n)=\sum _ {i=1}^{n} \binom{n-1}{i-1} F(i)S(n-i)$$
一个叫拆组合数的常见技巧。
$$S(n)=\sum _ {i=1}^{n} \frac{(n-1)!}{(i-1)!(n-i)!} F(i)S(n-i)$$
$$\frac{S(n)}{(n-1)!} = \sum _ {i=1}^{n} \frac{F(i)}{(i-1)!}\frac{S(n-i)}{(n-i)!} $$
卷积咯。
我们令
$$ A(x)=\sum \frac{S(x)}{(x-1)!} $$
$$ B(x)=\sum \frac{F(x)}{(x-1)!} $$
$$ C(x)=\sum \frac{S(x)}{(x)!} $$

$$ A(x)=B(x)C(x) $$
考虑我们若要求的是
即我们要在意义下求出

考虑多项式求逆
若求出的每一项的复杂度为
那么总复杂度为
小问题:关于的常数项,,负数的阶乘是未定义的,我们考虑用直接搞。

〜暂时性的撒花了〜

Recent Posts

comments powered by Disqus