Original link: https://www.shuizilong.com/house/archives/luogu-p5827-%E7%82%B9%E5%8F%8C%E8%BF%9E%E9%80%9A%E5%9B% BE%E8%AE%A1%E6%95%B0/
There is a thing called labeled counting lemma. In fact, it explains the combination meaning of EGF convolution.
It is said to give two EGF, F(x), G(x), then F(x)*G(x) is the ordered pair of objects generated after the two objects are relabeled, for example, if C(x ) is a connected graph. Then C^k(x)/k! is a graph with k connected components, and the combination meaning of exp in EGF can be deduced further.
This question polynomial is easy to construct, because any graph can construct a block-cut tree~
The method is that we think that there is a root version of C(x), then the root node must be in a block, and we enumerate the size i of this block, then the rest of the block can be connected to a C(x). . This part is C(x)^(i-1), and then multiplied by b_i. . . This part can be expressed by exp.
The rest is the difficulty of this question, which is Lagrange’s theorem. . In fact, if you have a label tree, you should learn this. . It’s just that there are so many ways we can skip class in that problem. .
#include <lastweapon/poly>
using namespace lastweapon;
Poly H, HH;
int n;
LL C2(LL n) {
return n*(n-1)/2;
}
int b(int n) {
--n; if (!n) return 1;
Poly A(n); REP(i, n) A[i] = H[i] * -n;
Poly B = HH.mod(n) * A.exp();
return (B[n-1] * fac[n-1]).x;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
vector<int> q; DO(5) q.PB(RD()); n = *max_element(ALL(q)) + 1;
Poly C(n), G(n); REP(i, n) G[i] = Mint(2).pow(C2(i)), G[i] *= invFac[i]; C = G. log();
H = CD().log(); HH = HD();
for (auto i: q) printf("%d\n", b(i));
}
This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-p5827-%E7%82%B9%E5%8F%8C%E8%BF%9E%E9%80%9A%E5%9B% BE%E8%AE%A1%E6%95%B0/
This site is only for collection, and the copyright belongs to the original author.