• 原题链接

私认为本题目前的大众做法，即：将题目转化成匹配问题，绝对值贡献从跨越水平线的角度计算。它虽然能很好的让读者理解这么做是对的，但不能说清楚为什么要这样做。

而对于这类贡献是绝对值之和的题目，应该是有更系统化的切入方式：拆贡献。

考虑每个元素对怪异度的贡献，显然对于元素 $x$（这里不区分是位置还是值），若最后其作为小数，贡献为 $-x$，反之为 $x$。换句话说，每个数为哪种贡献只与另外元素的相对大小有关。

从小到大考虑，不难发现我们很难做到实时匹配算贡献。但延续上面的思路，我们实时决定当前元素是与前面的数配对还是与后面的数配对是容易的，而这已经足够。因为这样我们就可以通过提前计算贡献的方式得到怪异度的变化。

不妨完善这个思路，我们发现从前往后考虑到第 $i$ 个元素时，我们需要记录的无非是在它前面决定与后面的数匹配的元素数量，以及当前怪异度。值得注意的是，因为待匹配的位置和值数量一定相同，所以我们可以一起记录，于是用 $f_{i,j,k}$ 表示以上状态，我们考虑转移：

• $i$ 号位置与元素自己匹配：$f(i,j,k) \leftarrow f(i-1,j,k)$

• 二者都与后面的数匹配：$f(i,j,k) \leftarrow f(i-1,j-1,k + 2i)$

• 二者都与前面的数匹配：$f(i,j,k) \leftarrow f(i-1,j+1,k - 2i) \times (j+1)^2$

• 二者有一个与前面匹配，有一个与后面匹配：$f(i,j,k) \leftarrow f(i-1,j,k) \times 2j$

值得注意的是，在 dp 转移中，转移系数代表了具体与当前决策中哪个元素匹配（最后一项的 $2$ 是区分位置和值），读者应当不难理解。

一个细节是第三维应当包含负数，且令 $m$ 表示怪异度，上下界不应该是 $[-m,m]$ 而是 $[-n^2,n^2]$，这均是因为在转移过程中怪异度可增可减。

我认为这应该是本题较为自然的解法。如果喜欢请点赞让更多人看见。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=55,mod=1e9+7;
int n,m,f[N][N][N*N*2];
inline void add(int &x,int y){x+=y;x-=(x>=mod)*mod;}
int main()
{
	scanf("%d%d",&n,&m);
	f[0][0][N*N]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=i;j++)
			for(int k=-n*n;k<=n*n;k++)
			{
				add(f[i][j][k+N*N],f[i-1][j][k+N*N]);
				if(j) add(f[i][j][k+N*N],2ll*f[i-1][j][k+N*N]*j%mod);
				if(j&&k+i*2<=n*n) add(f[i][j][k+N*N],f[i-1][j-1][k+i*2+N*N]);
				if(j<i-1&&k-i*2>=-n*n) add(f[i][j][k+N*N],1ll*(j+1)*(j+1)*f[i-1][j+1][k-i*2+N*N]%mod);
			}
	printf("%d",f[n][0][m+N*N]);
	return 0;
}