题意：设 将长为 的排列
当成置换时所能分解成的循环个数。给定两个整数 和一个 次多项式，对 分别求：
其中 是长度为 且不存在位置 使得 的排列。
，，时限 。
考虑对
分别求出循环个数为
的错排的个数。然后多点求值得到贡献系数即可算出答案。
考虑如何用生成函数刻画错排。错排可以看做大小 的循环组成的无序集合。
大小 的循环的 ：
错排的 :
我们要根据循环个数分类，于是改写为二元函数 。
我们的目标即是求出 ，然而
的次数上界和 有关，没有利用题目中
较小的性质。
将多项式
改写为牛顿级数，这部分容易
暴力完成。
然后分项求和，即对于 ，求
我们只需将生成函数改写为 。其中的 表示对于每个循环可选可不选。
此时，求出 再与
的系数（只有
个）点乘即可得到最终答案。
考虑系数递推。
边界为 。
按照上式递推即可，使用前缀和优化并滚动数组，复杂度为 。