这是一个标题

· · 题解

没意思的缝合怪。

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 时间下完成。