P10881
额三次方过 1000，数据不好评价，但是题目是神仙题。有一定技巧性，我做不出来就是了。不知道场上写出多项式做法的都是什么神仙。
大概是个矩阵树是吧，但是是基环树。就是基环树要么破环为链，要么缩环为点。那破环会算重，然后容斥也不知道有没有前途。考虑缩点。
那首先可以暴力枚举环所在的集合，然后剩下来的矩阵树。
优化从矩阵树的行列式计算开始。记 \(sum:=\sum_{i=1}^n a_i\)。
考虑 Laplace 矩阵的主子式，不妨撇掉缩点所在的一行一列。注意到邻接矩阵很特殊，任意三行线性相关。那考虑对主子式做低秩矩阵分解，分出来的邻接矩阵 \(A\) 只可能以小于等于两行的数量替换到 \(D\) 里面去。
然后这个 \(D\) 只在主对角线有值。所以替换之后的矩阵的行列式是好算的。
现在我们发明了平方计算行列式。具体地，可能会出现 \((na_i-sum),a_i,a_i^2,a_ia_j\) 这些因子。
考虑优化。瓶颈显然在环的枚举上。用一个 DP 统一计算贡献。
考虑环的贡献形式：\((a_1+a_2)(a_2+a_3)\dots(a_n+a_1)\)。显然每个 \(a_i\) 只会贡献 \(0/1/2\) 次幂，然后 \(0\) 和 \(2\) 次幂的个数是相等的。
（可以理解为，每个括号中取因子，可以看做给边定向，入度就是贡献次数。这样的小巧思多来点。）
通过这个小巧思，可以看出，设 \(0/1/2\) 次幂的分别取了 \(a,b,c\) 个，那么能构成的环的个数就是后面忘了。可以理解是，往长为 \(a\) 的圆排列里面，在 \(a\) 个空隙中插入 \(c\) 个元素（\(a\ne c\) 时答案自然是 \(0\)），每个空隙恰插入一个。然后再在 \(2a\) 个空隙中插入 \(b\) 个元素，允许空。然后钦定顺序。（推这个一定要快！）
然后 DP 的时候弄一个 \(f_{i,a,b,c,p,q}\) 表示，前 \(i\) 个，钦定了 \(a,b,c\) 个 \(0/1/2\) 次幂的环内元素，钦定了 \(p,q\) 作为行列式中替换集合。然后这个 \(p,q\) 是不需要记的因为可以多开 \(O(1)\) 维表示平方项的贡献，或者，我钦定 \(q\) 之前得钦定 \(p\) 吧，那钦定的时候直接在这个基础上乘就好了。
那现在有四次方做法了。好写吗？好像还行。
继续优化。考虑我们为什么要记录 \(a,b,c\)，还不是为了最后统计答案的时候算贡献系数。
那我们假如只知道全局的 \(0/1/2\) 次幂的个数，可不可以直接算系数？
可以的。注意到，环外部分的贡献，也可以写成关于 \(a_i\) 的 \(0/1/2\) 次幂的单项式（视 \(sum\) 为常数，即系数的一部分）的和。那我们只需要把每个这样的单项式的系数算出来就好了。
然后注意到由上面的分析，\(a,b,c\) 相同时（这里的 \(a,b,c\) 是全局的 \(0/1/2\) 次幂的个数），系数是相同的。好搞。因为这里 \(a,b,c\) 统计的是全局的个数，所以 \(a+b+c=n\)，又去掉了一维。复杂度三次方。