[清华集训2012]串珠子
接下来我们把整道题的主要思路简要地梳理开来。
首先,我们先考虑最经典的问题(这经典吗???):
旅行商问题
不,是与之类似的一类问题:给一堆点(有顺序要求),要求有多少种方案数使这 \(n\) 个点构成一张连通图(无自环、重边)。
该问题可以通过一下方法解决:
考虑补集转化思想,将求所有的连通图的方案转化为所有图的方案\(-\)非连通图的方案。
我们可以定义一个 \(dp(S)\) 代表最终答案( \(S\) 代表点集,下同),\(f(S)\) 代表非连通图的方案,\(g(S)\) 代表总方案数。
很显然,在该集合中所有的点构成的完全图的的子图个数是总方案数。
而对于非连通图而言,我们可以将点集中的点分为两部分——一部分为连通图、另一部分瞎搞,只要这两部分互相不连通就可以了。
只不过为了不重不漏,我们可以对于任意一个点,考虑它所在的连通图的节点个数进行计数。
最后我们有:
\[f(S)=\sum dp(S0)*g(S\setminus S0) \]回到这道题,我们可以仿照刚才的想法,补集转化去做。只不过我们这里的总方案数并不是2的整数次幂,而是每条边种数加一后,所有数的乘积后的结果。
对于补集而言,仍然选任意一个点进行分情况计数即可。
最后不用卡常就过了。
总结:
-
经典状压问题的变形;
-
补集转化。