[[清华集训2012]串珠子]

[清华集训2012]串珠子


接下来我们把整道题的主要思路简要地梳理开来。


首先,我们先考虑最经典的问题(这经典吗???):

旅行商问题

不,是与之类似的一类问题:给一堆点(有顺序要求),要求有多少种方案数使这 \(n\) 个点构成一张连通图(无自环、重边)。

该问题可以通过一下方法解决:

考虑补集转化思想,将求所有的连通图的方案转化为所有图的方案\(-\)非连通图的方案。

我们可以定义一个 \(dp(S)\) 代表最终答案( \(S\) 代表点集,下同),\(f(S)\) 代表非连通图的方案,\(g(S)\) 代表总方案数。

很显然,在该集合中所有的点构成的完全图的的子图个数是总方案数。

而对于非连通图而言,我们可以将点集中的点分为两部分——一部分为连通图、另一部分瞎搞,只要这两部分互相不连通就可以了。

只不过为了不重不漏,我们可以对于任意一个点,考虑它所在的连通图的节点个数进行计数。

最后我们有:

\[f(S)=\sum dp(S0)*g(S\setminus S0) \]


回到这道题,我们可以仿照刚才的想法,补集转化去做。只不过我们这里的总方案数并不是2的整数次幂,而是每条边种数加一后,所有数的乘积后的结果。

对于补集而言,仍然选任意一个点进行分情况计数即可。

最后不用卡常就过了。


总结:

  1. 经典状压问题的变形;

  2. 补集转化。

上一篇:[真题解析]广州大学2012年高等代数考研试题参考解答03用反证法推理时定要有理有据!


下一篇:[NOI 2012] 骑行川藏