自动搬运

查看原文

来自洛谷，原作者为

	Union_of_Britain 神于天

搬运于2025-08-24 22:59:04，当前版本为作者最后更新于2024-06-19 19:24:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先考察操作的性质。

注意到若设每个点的势能是 $|i-p_i|$，一次代价为 $W$ 的操作的最多使得总势能减少 $2W$。因此有不等式：

这个形式看起来就很正确。猜想其可以取到下界，所以有：

引理 1：一个排列的最小交换代价是 $\dfrac{\sum |i-p_i|}{2}$。

证明：

只需说明对于每个非恒等的排列有一个使总势能减少 $2W$ 的操作即可，然后施加归纳法即可。设原排列为 $p$，逆排列为 $r$，则等价于存在：

取 $i$ 为最小的 $i\neq p_i$，$j$ 为 $[i,r_i]$ 中一个 $k$ 使得 $p_k\ge r_i$ 即可。这样的 $i,j$ 总是存在的。

再考虑“交换 $n$ 次”是什么意思。不难发现：

引理 2：可以交换 $n$ 次到达的排列是所有奇偶性等于 $n$ 的奇偶性的排列。

这是容易证明的：奇偶性不等于 $n$ 的排列显然无法到达，奇偶性相等的排列可以构造：每次操作直接从后面交换即可（如果需要）。最后剩下的次数是偶数，一直操作 $(1,2)$ 即可。

奇排列和偶排列的答案应该不会差太远，并且应该具有某种模式。打表不难发现：

引理 3：对于 $\sum |i-p_i|=2k$ 的排列，奇偶排列的个数差的绝对值是 $\binom{n-1}{k}$，并且正负性是 $(-1)^{n+k}$。

证明（不过显然考试时这个结论是没有必要证明的）：考虑建立一个使得势能和不变的奇偶排列的映射。如果存在一个使势能和不变的交换就交换一次，这样的映射显然可逆，这样只需考虑那些不能交换的。

那些不能交换的就是循环都由连续数字构成的排列。设有 $m$ 个循环，则势能和应该是 $2(n-m)$，而计数是 $\binom{n-1}{m-1}=\binom{n-1}{n-m}$。

这样问题就被几乎转化为 ABC134F。然后我们队在做的时候看到数据范围就不知道怎么做了。

事实上这里的 DP 就是采取 ABC134F 的方法。比如这一篇题解。但是那道题的时间复杂度是 $O(n^2m)$，似乎难以通过。

但是本题具有更特殊的性质：$m$ 量级小于 $n^2$。仔细分析这篇题解的状态，应该有 $j$（第二维）是 $O(\sqrt m)$ 的，只是由于那道题的 $m=n^2$ 才没有改变复杂度。

这样最后的复杂度就是 $O(nm\sqrt m)$，可以通过。

注：代码里的状态实际上是官方题解的状态，也就是说这个代码的 $j$（代码里是 $d+i$）是上面那篇题解的 $i-j$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int T,n,m,N=500,M=10000,SM=80;
int f[2][160][10005],fac[100005],ifac[10005];
int qp(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
inline int C(int a,int b){
	if(b>a)return 0;
	return fac[a]*ifac[b]%mod*ifac[a-b]%mod;
}
int s[505][20005];
inline int pow1(int x){
	if(x&1)return mod-1;
	return 1;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	fac[0]=1;
	for(int i=1;i<=M;i++)fac[i]=fac[i-1]*i%mod;
	ifac[M]=qp(fac[M],mod-2);
	for(int i=M-1;i>=0;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
	int I2=(mod+1)/2,cur=0;
	f[cur][0][0]=1;
	for(int i=1;i<=N;i++){
		cur^=1;
		for(int d=0;d<=min(SM,i);d++){
			for(int k=(d-1)*d;k<=M;k+=2){
				f[cur][d][k]=0;
				if(d>0)f[cur][d][k]=f[cur^1][d-1][k-2*(d-1)];
				if(k>=2*d)f[cur][d][k]+=f[cur^1][d][k-2*d]*(2*d+1);
				if(f[cur][d][k]>=mod)f[cur][d][k]-=mod;
				if(k>=2*(d+1))(f[cur][d][k]+=f[cur^1][d+1][k-2*(d+1)]*(d+1)*(d+1))%=mod;
			}
		} 
		for(int j=0;j<=M;j++){
			if(j&1)continue;
			int k=j/2,F=f[cur][0][j];
			if(k<=i)(F+=pow1((i&1)+(k&1))*C(i-1,k)%mod)%=mod;
			F=F*I2%mod;
			s[i][j]=((j>0?s[i][j-2]:0)+F)%mod;
		}
	}
	cin>>T;
	while(T--){
		cin>>n>>m;
		int ans=s[n][m*2];
		cout<<ans<<endl;
	}
	return 0;
}