题解：P17341 【MX-X30-T7】言而无信者的救赎
lailai0916
·
·
题解
题意简述
把排列的位置和值分别按 (2i-1,2i) 分成 n 个块。若一个位置块恰好映射到某个值块，称它为好块。对每种好块数和置换环数，求对应排列数，最后按题意异或。
解题思路
用 x 记录置换环数。设 D_m(x) 为 2m 个元素的全坏块排列生成函数。
设 E_m(x) 为 2n 个元素的排列生成函数。其中指定的前 m 个块为坏块，其余块为好块。
从一个含有 t 个块的排列加入一个指定的好块。可以让两个新元素分别成为自环，增加两个置换环；也可以选择原来的一个块，把新块插入对应的两条边，不改变环数。删除这个好块能唯一还原原排列，因此转移因子为 x^2+t。于是：
E_m(x)=D_m(x)\prod_{t=m}^{n-1}(x^2+t)
特别地：
E_0(x)=\prod_{t=0}^{n-1}(x^2+t)
下面递推 D_m(x)。在置换环表示中依次插入两个新元素。每个元素可以单独形成一个环，也可以插入当前任意一条有向边。反过来，从所有块均坏的排列中删除最后两个元素，至多会让原来的两个块恢复为好块。
设删除后有 r 个好块。按两个新元素中形成自环的个数分类，满足插入后所有块均坏的方案数如下：
| r |
不形成自环 |
形成一个自环 |
形成两个自环 |
| 0 |
4m^2 |
4m+1 |
0 |
| 1 |
8m-3 |
4 |
0 |
| 2 |
8 |
0 |
0 |
表中的计数可以直接从插入位置得到。r=0 时，不形成自环共有 2m(2m+1) 种，其中 2m 种会产生好块。形成一个自环有 2m+(2m+1) 种。
$r=2$ 时，两个元素必须分别覆盖两个好块。选择各自覆盖的边和插入顺序，共有 $8$ 种。若 $r>2$，两个元素无法破坏全部好块。
删除后恰有 $r$ 个好块的生成函数，分别为：
- $r=0$：$D_m(x)$。
- $r=1$：$m(x^2+m-1)D_{m-1}(x)$。
- $r=2$：$\binom{m}{2}(x^2+m-2)(x^2+m-1)D_{m-2}(x)$。
结合插入方案数可得：
$$
\begin{aligned}
D_{m+1}(x) & =(4m^2+(4m+1)x)D_m(x) \\
& +m(x^2+m-1)(4x+8m-3)D_{m-1}(x) \\
& +4m(m-1)(x^2+m-2)(x^2+m-1)D_{m-2}(x)
\end{aligned}
$$
代入 $E_m(x)$ 的定义并约去公共乘积，得到实际使用的递推：
$$
\begin{aligned}
(x^2+m)E_{m+1}(x) & =(4m^2+(4m+1)x)E_m(x) \\
& +m(4x+8m-3)E_{m-1}(x) \\
& +4m(m-1)E_{m-2}(x)
\end{aligned}
$$
令 $e_{m,j}=[x^j]E_m(x)$，$r_{m,j}$ 为上式右侧的 $x^j$ 项系数。按次数从高到低计算：
$$
e_{m+1,j}=r_{m,j+2}-me_{m+1,j+2}
$$
这个顺序不需要除以 $m$，也自然覆盖 $m=0$。递推只依赖前 $3$ 行，可以使用滚动数组。
一个置换的最少交换次数为 $2n-c(p)$。一次交换至多使两个块变坏，所以含 $m$ 个坏块时，环数至多为 $2n-\lceil\frac{m}{2}\rceil$。代码只枚举到这个次数上界，其余系数均为 $0$。
若原排列恰有 $i$ 个好块，先选择这些块，再使用 $E_{n-i}(x)$ 计数。因此：
$$
H(i,j)=\binom{n}{i}[x^j]E_{n-i}(x)
$$
计算出每一行后即可立刻加入异或答案。时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=4005;
const int M=8005;
const int mod=1000000007;
int fac[N],ifac[N];
int f[4][M],g[M];
ll Pow(ll x,ll y)
{
ll res=1;
while(y)
{
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
int C(int n,int m)
{
return (int)((ll)fac[n]*ifac[m]%mod*ifac[n-m]%mod);
}
void solve()
{
int n,d;
cin>>n>>d;
for(int i=0;i<4;i++)fill(f[i],f[i]+2*n+3,0);
f[0][0]=1;
for(int i=0;i<n;i++)
{
for(int j=2*i+2;j>=0;j--)
{
ll res=(ll)f[0][j]*i;
if(j>=2)res+=f[0][j-2];
f[0][j]=(int)(res%mod);
}
}
int ans=0;
for(int j=1;j<=2*n;j++)ans^=d+f[0][j];
for(int i=0;i<n;i++)
{
int cur=i&3,nxt=(i+1)&3,b=i+1,z=(b+1)/2,deg=2*n-z,top=deg+2;
ll p=4LL*i*i%mod,q=(4LL*i+1)%mod,r=(ll)i*(8LL*i-3)%mod;
ll s=4LL*i%mod,t=4LL*i*(i-1)%mod;
for(int j=0;j<=top;j++)
{
ll res=(ll)f[cur][j]*p;
if(j)res+=(ll)f[cur][j-1]*q;
if(i>=1)
{
int pre=(i-1)&3;
res+=(ll)f[pre][j]*r;
if(j)res+=(ll)f[pre][j-1]*s;
}
if(i>=2)
{
int pre=(i-2)&3;
res+=(ll)f[pre][j]*t;
}
g[j]=(int)(res%mod);
}
f[nxt][deg+1]=0;
f[nxt][deg+2]=0;
for(int j=deg;j>=0;j--)
{
ll res=g[j+2]-(ll)i*f[nxt][j+2]%mod;
if(res<0)res+=mod;
f[nxt][j]=(int)res;
}
int mul=C(n,b);
for(int j=1;j<=deg;j++)
{
int val=d+(int)((ll)mul*f[nxt][j]%mod);
ans^=val;
}
if(z&1)ans^=d;
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
fac[0]=1;
for(int i=1;i<N;i++)fac[i]=(int)((ll)fac[i-1]*i%mod);
ifac[N-1]=(int)Pow(fac[N-1],mod-2);
for(int i=N-1;i;i--)ifac[i-1]=(int)((ll)ifac[i]*i%mod);
int t;
cin>>t;
while(t--)solve();
return 0;
}
```