杂题

题意

(n)个人在玩分组游戏，有(c)个组可以选择，相邻两人不能去同组。同时，有(k)个人之间可能还有(m)个限制条件，使得其不同处于同组。求方案数
(n,cle 2^{60},kle 20,mle {kchoose 2})

做法

将(k)个人称为特殊点，考虑固定分组后的两个相邻的特殊点，令其间有(len)个普通点，可根据两个特殊点组是否相同用矩阵快速幂算出其方案数

枚举在同一组的特殊点，其对方案数的影响很容易能得出
可以看到子集卷积可以解决

暴力枚举特殊点分成了多少组，复杂度是(O(k^32^k))的

将单个组贡献写成集合幂级数(F(x))，(ans=[x^{2^U}]sumlimits_{i=1}^k {cchoose i}F(x)^i=[x^{2^U}]sumlimits_{i=0}^k {cchoose i}F(x)^i=[x^{2^U}](F(x)+1)^c)
于是可以(O(n^22^n))计算

题外话

把一个**题误认为是神仙题了...