某岛

… : "…アッカリ~ン . .. . " .. .
July 13, 2015

Graphical Enumeration

有标号仙人掌

例题「LOJ #161」仙人掌计数

???+ note ” 例题 「LOJ #161」仙人掌计数
题目大意:仙人掌是一张无向连通图,在一个仙人掌上,任意一条边至多只会出现在一个环上。求含有 n 个结点的有标号仙人掌的方案数。

有标号荒漠

例题「Luogu P5434」【模板】有标号荒漠计数

???+ note ” 例题 「Luogu P5434」【模板】有标号荒漠计数
题目大意:荒漠是一张无向图,一个荒漠的每个极大连通分量都是一个仙人掌。求含有 n 个结点的有标号荒漠的方案数。

无标号二叉树

例题「CodeForces 438 E」The Child and Binary Tree

参考资料

四重计树法

解决一堆问题往往比解决一个孤立的问题有效,特别是前者我们所选择的问题彼此相关的时候。类比之前的 十二重计数法,我们可以提出四重计树法来打包处理以下四个问题:

  • 有标号有根树
  • 有标号无根树
  • 无标号有根树 Euler 变换 A000081
  • 无标号无根树 考察重心 A000055

这里最终的核心其实只有最后这个问题。

相关的例题是 SPOJ. PT07DLuogu. 5900,前者恰好就是四重计数法,不过数据规模很小而且模数任意,不适合直接跑各种多项式的板子,结果推倒完反而更类似 dp。后者更适合用来测试模板。

有标号

Trivial
Matrix67, 经典证明:Prüfer编码与Cayley公式
Wikipedia, Prüfer sequence
https://www.luogu.com.cn/problem/P5219 度限制

二叉树

二分图

连通图

DAG

有标号

有标号、若连通

基环树

仙人掌

http://www.math.ucla.edu/~pak/hidden/papers/Moon-counting_labelled_trees.pdf

http://math.stackexchange.com/questions/689526/how-many-connected-graphs-over-v-vertices-and-e-edges
Level 1.
http://www.matrix67.com/blog/archives/682

Level 2.
http://poj.org/problem?id=1737

Level 3.
http://www.spoj.com/problems/KPGRAPHS/
https://www.hackerrank.com/contests/infinitum-sep14/challenges/strongly-connected-digraphs

Other:

生成树计数
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=648&page=show_problem&problem=5150

http://user.qzone.qq.com/251815992/blog/1380986878 (仙人掌图计数。。???)
https://projecteuler.net/problem=434
http://hihocoder.com/contest/challenge2/problems
http://hihocoder.com/discuss/question/591

“ 我十分有幸参加了这场500人斩比赛并贡献一WA ”。。