大鸽子更博了！
有 \(2^n\) 个人，每次相邻比试，比试到只剩一人。\(x<y\) 时 \(x\) 获胜。\(1\) 选手想获胜，但它会输给其中 \(m\) 个选手。求初始序列的方案数。
\(n,m\le 16\)
一道状压 \(dp\) + 容斥原理的好题。
（居然是自己想出来的）
\(f_{i,j}\) 表示给定选手 \(i\sim m\) 决定是否强制为集合的最小值时，集合大小 \(2^0,2^1,...,2^{n-1}\) 选择的情况。
\[f_{i,j}\times {2^n-a_{i-1}-j \choose k-1}\times k!\rightarrow f_{i-1,j|2^k}[j\&2^k=0]\]
\[ans=2^n\times \sum_S(-1)^{|S|}(2^n-1-S)!*f_{1,S}\]
给定一个无向连通图 \(G\)，问其诱导子图连通的方案数，对 \(2\) 取模。
\(n\le 50,1\le |a-b|\le 12\)
注意到一个图，有 \(k\) 个连通块，那么它黑白染色的方案数为 \(2^k\)。
我们先求子图黑白染色的方案数，因为连通块 \(ge 2\) 时须忽略，故对 \(4\) 取模除二即为答案。
状态就很简单了：黑色，白色，不选。时间 \(O(n3^{12})\)。其实 \(n^23^{12}\) 也跑得过去。。。
相当于在 \(k\) 个集合中，每个集合大小为 \(a_i\)，各选一个的方案数。
比如 神佬来切切吧
\(\text{WC2019}\) 数树更是结合了 \(\text{prufer}\) 序列的推论：\(k\) 个连通块，\(\sum_{i=1}^{k}a_i=n\)，方案数为 \(n^{k-2}\prod_{i=1}^{k}a_i\)。
这是一道不可多得的好题！
原文：https://www.cnblogs.com/owencodeisking/p/12247013.html