AT_pakencamp_2018_day2_g Sol || 人类智慧 1.5

· · 题解

写篇题解记录一下目前我在 OI 赛制中自己搞出来的最难计数题。因为我不知道广义串并联图是什么，所以使用一些比较朴素的计数方法。

因为这个做法时间复杂度基本全是常数，所以复杂度就不加 O() 了。

考虑 m=n-1。是一棵树，答案显然为 k\cdot(k-1)^{n-1}。从根开始每个点保证和父亲不同即可。

考虑 m=n。是一棵基环树。环上像树那样染色可能会导致头尾颜色撞车，但环外是一样的。设环外点数为 oth，环上方案数 w，答案为 w(k-1)^{oth}。实际上环上的部分也较为容易，选一个起点然后 dp_{i,0/1} 表 i 点颜色是否和起点相同的方案数。跑一遍就可以了。

考虑 m=n+1。然后大脑皮层就打结了。

考虑抽象一点。在图上先找一棵生成树。对于非树边，设其为关键边，连接的点设为关键点。那么关键点最多只有 8 个。我们假设它就是 8 个，少了也差不多。现在问题变成，给树染色，相邻两点颜色不同，4 条关键边连接的两点颜色也不同，问方案数。

这个东西看起来非常容斥。确实是可以的，但是在容斥之前我们就可以通过本题。

结合刚才思考 m=n DP 的一些发现可以得到这么一个事实：一条链，只要链长和头尾颜色固定，那么中间其它点的染色方案数具体是多少，只取决于链的头尾颜色是否相同。这个具体的方案数可以用那个 m=n 的 DP 直接对每个链长预处理出来。

这启发我们求关键点的虚树以简化这棵树的形态，反正链的贡献只要知道两端颜色是否相同就知道了。那么虚树最多有 15 个点，称上面的是虚树点。注意区分虚树点和关键点。后者被前者包含。

实际实现时直接 dfs 求虚树即可。

不在虚树上的点计入 oth 最后再算贡献。记录一下每条虚树边对应的原树路径上有多少个点。称每条虚树边对应的原树路径为中间路径，路径上除两端（虚树点）外的点为中间点。

那么链的结论放到虚树上，只要我们确定了每两个虚树点的染色是否相同，那么每条中间路径的染色方案数都是确定且容易求得的，不管虚树点具体染的是什么颜色，只要知道它相不相同就够了。

考虑把 15 个虚树点划分为若干个集合，令每一个集合内染色相同，不同集合染色不同。枚举划分方案，毙掉不合法的（有关键边连了相同颜色的点）。对每一种合法划分方案去求每条中间路径的染色方案数，以及这些虚树点自己有多少种分配颜色的方案（因为我们只枚举了相同情况，具体颜色不知道），这都是非常容易求得的。加起来就是答案。

而划分方案数是 \operatorname{Bell}(15)>10^8。丸辣！考虑优化。

这 15 个虚树点里面有 7 个不是关键点，它们是被其它关键点生成出来的。而我们费这么大劲去枚举划分方案，无非就是想防止不合法的情况混进去。但是情况不合法只是因为某几对关键点相同了，跟这 7 个非关键点的虚树点有什么关系呢？

考虑能不能只划分那 8 个关键点，然后把 7 个剩下的虚树点的颜色也一起计数。设现在有一种划分方案，关键点 i 被分配到 c_i 集合，总共有 lim 个集合。

这里可以在虚树上 DP。设 dp_{i,j} 表示 i 自己染的颜色种类是 j，i 子树中除 i 以外的染色方案数。其中 j\in [1,lim] 表示 i 点和关键点划分的第 j 个集合颜色相同，j=0 表示它和任何一个集合颜色都不同。

那个除 i 以外的限制是因为，结合下面转移细节，我们在把 i 的信息合并到它的（虚树）父亲上时，需要处理连接它们的这条中间路径的染色方案数，那就需要知道父子颜色是否相同。但是 j=0 代表了 k-lim 种颜色，如果提前把它染色了，我在父亲上是没法具体知道它到底染的哪一种的，也就不好处理相不相同。所以把 i 自己的颜色放到它的父亲上考虑是更为妥当的选择。

转移大概就是，对于一对父子 (u,v) 的 dp_{u,i} 和 dp_{v,j}，我们得到 dp_{v,j} 之后要把它们合并起来得到一个新的 dp'_{u,i}。然后分 u,v 的颜色是否相同去讨论一下，得到相同和不同时 v 自己和 u\to v 这条中间路径上的染色方案数。这个 DP 大概是 9\cdot 15^2 的。

把 dp_{1} 各项乘上 1 自己的染色方案数拿出来就是答案了。这样我们就 \operatorname{Bell}(8)\cdot 9\cdot 15^2 地通过了此题。AC 代码。比大部分广义串并联图做法都快。也难写一些。

但还有高手。现在我们把 m-n 开到 5。

于是这个做法变成了 \operatorname{Bell}(12)\cdot 13\cdot 23^2。\operatorname{Bell}(12)>10^6，即使只划分 12 个关键点也会显得非常难受，实测常数也不够小。考虑怎么办。

之前提到过这个问题形式非常适合容斥。考虑容斥一下，枚举关键边集合，强制使里面的边不满足条件（连接两点颜色相同），计数。设被选中的点为特殊点。注意区分特殊点和之前的关键点，没有和容斥钦定的边相连的关键点是不计入特殊点的。

那么现在问题变成：树上相邻不同染色，其中有若干组特殊点，限制每一组内的颜色都必须相同。问方案数。特殊点个数 \le 12，组数 \le 6。

考虑类似的做法。跟容斥之前把关键点的虚树扒出来一样，现在把特殊点的虚树扒出来，大小最多 23。然后枚举特殊点相同情况的划分方案，分别虚树上 DP 求值。但和之前不同的是，因为限制了组内颜色相同，所以这次是对特殊点组进行划分，而组数只有 6！

可以理解成我们用容斥把点集合转移到了边上，成功规避掉了钦定集合数过多的情况。于是每次跟刚才跑一样的 DP 做法就好了。每次做完乘上容斥系数加回去。

变成 2^6\cdot\operatorname{Bell}(6)\cdot 7\cdot 23^2。这是比不容斥要优秀得多的。此题容斥代码，代码里是对关键点（而不是特殊点）建的虚树，没啥影响，而且对每个容斥集合都是一样的，方便一点。