自动搬运

查看原文

来自洛谷，原作者为

	MatrixCascade 青箔镜中朱颜改，去年今日桃花红。

搬运于2025-08-24 22:22:52，当前版本为作者最后更新于2022-08-06 02:23:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

没意思的缝合怪。

Subtask1 直接暴力 dfs，好像还得剪枝不然过不去。

Subtask2 直接状压 dp，设 $dp_{i,j}$ 表示 i 这个状态中的所有小孩用了正好 j 种玩具的方案数，预处理出 $f_i$ 表示 $i$ 这个集合里面可以用同一种玩具，$dp$ 转移的时候使用子集枚举加速即可，虽然查询中的玩具总数会很多，但是你最多用到 $n$ 种。$dp$ 数组预处理出来，查询再加个组合数即可。

Subtask3 是边数很小，这提示我们用边数相关的做法。直接枚举 钦定 $S$ 集合里面的边强制同种颜色的方案数，答案就是 $k^w$，$w$ 是连通块个数，于是你只要把连通块个数为 $j$ 的系数预处理出来就行了，每次查询就是 $O(m)$ 的。

注意预处理的实现要精细一点，可以用 dfs 枚举状态+可撤销并查集。如果实现不好很容易被卡常。

Subtask4 不难发现是形成若干个环，但是你只需要考虑环的长度即可。然后就有一个用烂了的套路是本质不同的环的个数只有 $\sqrt n$ 个，把同类环合并就可以了。

在考虑如何求 $f(n,k)$ (n 个点的环用 k 种颜色的方案数，相邻不同色)先看看这个东西能不能递推。考虑枚举第一个点和第 $n-1$ 个点颜色是否一样，如果颜色一样，那么首先 $n$ 号点有 $k-1$ 种取值，然后你可以把 $1,n,n-1$ 合并起来看成一个点，剩下的就为 $f(n-2,k)$ ; 如果颜色不一样，那么 $n$ 号点有 $k-2$ 种取值，然后你可以把 $n$ 号点扔掉，就变成了 $f(n-1,k)$。 (因为你强制了 1 号不等于 n-1 号)

于是就有了递推式 : $f(n,k)=(k-2)f(n-1,k)+(k-1)f(n-2,k)$。

发现是只与前两项有关的递推 ! 解一下特征方程就可以得到 $f(n,k)=(k-1)^n+(k-1) \times(-1)^n$。

再加上本质不同的环合并，每次查询就可以在 $\sqrt n \times \log$ 时间下完成。