Luogu P5827. 点双连通图计数

原文链接： 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/

• https://www.luogu.com.cn/problem/P5827

有一个东西叫做 labeled counting lemma。其实就是交代了 EGF 卷积的组合意义。

说的是给两个 EGF，F(x), G(x)，那么 F(x)*G(x) 就是这两个对象重新标号之后所生成的对象的有序对，比如如果 C(x) 是连通图。那么 C^k(x)/k! 就是有 k 个连通分量的图，进一步就能推出 EGF 里 exp 的组合意义。

这个题多项式很容易构建，因为任意图都可以构建出 block-cut tree~

方法是我们思考有根版本的 C(x)，那么这个根节点一定在一个 block 里，我们枚举这个 block 的 size i，那么这个 block 剩下的部分都能连一个 C(x)。。这部分就是 C(x)^(i-1)，然后再乘以 b_i 就好。。。这个部分可以用 exp 表达。

剩下的是这个题的难点，就是拉格朗日定理。。其实有标号树就应该要学会这个。。只是那个问题里我们有太多方法可以逃课。。

 
  
#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 = C.D().log(); HH = H.D(); 
  
 
  
    for (auto i: q) printf("%d\n", b(i)); 
  
} 
  
 
  

本文转自： 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/
本站仅做收录，版权归原作者所有。