题解：P17341 【MX-X30-T7】言而无信者的救赎
WorldMachine
·
·
题解
来点不需要任何分讨的纯代数做法。
前面的讨论和官方题解是一样的。
将 (2i-1,2i) 看成一块，称符合题目要求的为好块，即两条出边平行地指向同一个块 (2j-1,2j)。
块之间可以随意交换顺序，不妨钦定前 m 个块是坏的，后 n-m 个块是好的，最后统计答案时乘上 \dbinom nm 即可。
设 F_m(x) 表示符合如上要求的排列 p 的 x^{\text{cyc}(p)} 之和。
二项式反演，让前 2m 个点乱连，再把后面 n-m 个好块插进去，前者的 OGF 显然是 x^{\overline{2m}}，要考虑的就是插一个好块带来的影响。
好块自己连自己不会影响别人，会多出来 2 个环，贡献 x^2；否则插在已有的某个块前面：
Before : u -----------------> (2b - 1)
v -----------------> ( 2b )
After : u ---> (2k + 1) ---> (2b - 1)
v ---> (2k + 2) ---> ( 2b )
发现不会影响其它块的好坏，也不会产生新的环，假设之前有 k 个块，贡献 k。因此插一个好块的影响是 x^2+k。
因此不限制坏块的 OGF 是 G_m(x)=x^{\overline{2m}}(x^2+m)^{\overline{n-m}}，根据定义有：
G_k(x)=\sum_{m=0}^k\binom kmF_m(x)\implies F_m(x)=\sum_{k=0}^m(-1)^{m-k}\binom mkG_k(x)
照着式子直接算即可做到 \mathcal O(n^3)。
考虑优化。
首先有：
\begin{aligned}
(x^2+k)G_{k+1}(x)&=(x+2k)(x+2k+1)G_k(x)\\
&=((x^2+x)+(4x+6)k+4k^{\underline2})G_k(x)
\end{aligned}
考虑魔法，把 \{G_k\} 写成 EGF 算子 \mathcal G，形式变元为 t，求导算子记为 D，满足 [t^m]t^aD^b\mathcal F(t)=m^{\underline a}F_{m-a+b}。
等式转写为：
(x^2D+tD^2)\mathcal G=((x^2+x)+(4x+6)tD+4t^2D^2)\mathcal G
$$
(x^2(D+1)+t(D+1)^2)\mathcal F=((x^2+x)+(4x+6)t(D+1)+4t^2(D+1)^2)\mathcal F
$$
按照偏移量（$D$ 的次数 $-$ $t$ 的次数）分类化简，可得：
$$
(x^2D+tD^2)\mathcal F=(x+(4x+4)tD+4t^2D^2)\mathcal F+((4x+5)t+8t^2D)\mathcal F+4t^2\mathcal F
$$
转写回来，注意是 $m^{\underline2}$ 而非 $m^2$，化简得：
$$
(x^2+m)F_{m+1}=(4m^2+(4m+1)x)F_m+m(4x+8m-3)F_{m-1}+4m(m-1)F_{m-2}
$$
直接递推即可，$F_0$ 用第一类斯特林数预处理，时间复杂度 $\mathcal O(n^2)$。
放个没卡常的代码。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef long long ll;
const int N = 4005, P = 1e9 + 7;
il void _a(int &x, int y) { (x += y) >= P && (x -= P); }
il void _d(int &x, int y) { (x -= y) < 0 && (x += P); }
int n, _, n2, C[N][N], S[N][N], f[N][N * 2], tf[N * 2];
void solve() {
cin >> n >> _, n2 = 2 * n;
for (int i = 0; i <= n; i++) fill(f[i], f[i] + 3 + n2, 0);
for (int i = 1; i <= n; i++) f[0][2 * i] = S[n][i];
for (int m = 0; m < n; m++) {
int d = n2 - (m + 1) / 2; fill(tf, tf + 3 + d, 0);
for (int i = d; ~i; i--) _a(tf[i], 4ll * m * m * f[m][i] % P), _a(tf[i + 1], (4ll * m + 1) * f[m][i] % P);
if (m) for (int i = d + 1; ~i; i--) _a(tf[i], m * (8ll * m - 3) * f[m - 1][i] % P), _a(tf[i + 1], 4ll * m * f[m - 1][i] % P);
if (m > 1) for (int i = d + 1; ~i; i--) _a(tf[i], 4ll * m * (m - 1) * f[m - 2][i] % P);
for (int i = d; ~i; i--) _d(f[m + 1][i] = tf[i + 2], (ll)m * f[m + 1][i + 2] % P);
}
int ans = 0;
for (int i = 0; i <= n; i++) for (int j = 1; j <= n2; j++) ans ^= (ll)C[n][i] * f[n - i][j] % P + _;
cout << ans << '\n';
}
int main() {
for (int i = 0; i < N; i++) { C[i][0] = 1; for (int j = 1; j <= i; j++) _a(C[i][j] = C[i - 1][j], C[i - 1][j - 1]); }
S[0][0] = 1; for (int i = 1; i < N; i++) for (int j = 1; j <= i; j++) S[i][j] = (S[i - 1][j - 1] + ll(i - 1) * S[i - 1][j]) % P;
ios::sync_with_stdio(0), cin.tie(0); int T; cin >> T; while (T--) solve();
}
```