首先和 \(\text{Fast as Ryser}\) 一样，当 \(n\) 为奇数时加一个点，将 \(n\) 任意划分成 \(\frac{n}{2}\) 个匹配，则求的匹配和原来的匹配构成了若干个环和若干条链，那么有匹配大小 \(=\) \(\frac{n}{2}-\) 链的个数。令链的集合幂级数为 \(F\)，环的为 \(G\)，现在问题转化为对于每一个 \(k\)，求 \(F^kG\) 在全集处的取值。但由于模数不为质数，对占位多项式的 \(\text{ln},\text{exp}\) 的阶乘逆元无法定义，直接对占位多项式操作是多项式复合，做到比 \(O(n^3)\) 优会非常复杂。
难道没有别的办法了吗？其实集合幂级数有一个神奇的性质，由于指数的增长速度是远比多项式的增长速度快的，有当 \(b>1\) 时 \(\lim_{x->\infty}\frac{x^a}{b^x}=0\)，所以我们如果能把复杂度化为形如 \(\sum_{i=0}^{n}(n-i)^ai^b2^i\) 的形式的话，那复杂度其实是 \(O(n^b2^n)\) 的，这是因为 \(\sum_{i\geqslant 0}i^a2^{-i}\) 其实是收敛的。
先考虑其转置问题，即求 \(\sum_{i=0}^{n}\frac{a_{i}}{i!}F^{i}e^G\)，根据前面的结论，如果我们从低位往高维 \(\text{dp}\)，第 \(i\) 位记录 \((n-i)^a\) 的状态，则复杂度只会乘常数。那么我们令 \(dp_{i,j,S}\) 表示考虑了前 \(i\) 位后后面的位用了 \(j\) 个 \(F\)，当前集合并为 \(S\) 的权值和，一开始将 \(dp_{0,i,0}\) 赋为 \(a_{i}\)，每次新加一个位，如果加入 \(F\) 则后面用的个数减少，加入 \(G\) 则后面用的个数不变，如果不加也不变。最后把这个算法转置一下就可以 \(O(2^nn^2)\) 了。