LibreOJ 155. Tutte 多项式 | Alpha1022's Blog

[Alpha1022]

https://www.alpha1022.me/articles/loj-155.htm

因为不太想写长篇笔记就随便记篇题解吧…… 我们考虑一个图 (G=(V,E)) 的 Tutte 多项式 [ T_G(x,y) = \sum\limits_{A\subseteq E} (x-1)^{k(A)-k(E)} (y-1)^{k(A)+|A|-|V|} ] 容易知道指数都是非负的，因此我们可以尝试给出一个在任意环上的算法。 首先我们知道其 Tutte 多项式等价于每个连通分量的 Tu