T5 [ABC134F] Permutation Oddness
很无敌的一道题。（好像是我第一次用无敌这个词
把 \(p_i\) 和 \(i\) 的对应关系转化为球和盒子的配对问题，则原式中的绝对值顺利成章地就变成类似距离的一个东西。
那么设 \(f_{i,j,k}\) 表示前 \(i\) 个球和盒子（注意球和盒子是一起考虑的，所以 \(i\) 只会遍历到 \(n\)）、其中有 \(j\) 组球和盒子暂未配对、当前怪异度为 \(k\) 的答案。则答案为：\(f_{n,0,K}\)。到这里应该是不难理解的。
考虑新遍历到一组球和盒子，会有三种情况出现：不给它们配对、给其中一个配对、给俩都配对。
情况一：不给它们配对。
则易得转移方程：
\[f_{i+1,j+1,k+2j}\gets f_{i,j,k} \]\(k+2j\) 是什么？以后再解释。
情况二：给其中一个配对。
- 如果给球配对，相当于用了之前的一个没有配对的盒子，有 \(j\) 种情况；
- 如果给盒子配对，相当于用了之前的一个没有配对的球，有 \(j\) 种情况；
- 还有一种特殊情况：直接将当前球和当前盒子配成一对，有 \(1\) 种情况。
综上，有 \(2j+1\) 种情况。易得任意一种都是用了一个没有配对的又多了一个当前的，或者是直接解决当前的且不管前面的，所以 \(j\) 不变，有转移方程：
\[f_{i+1,j,k+2j}\gets f_{i,j,k}\times(2j+1) \]情况三：给俩都配对。
当前的球有 \(j\) 个盒子给它配对，当前的盒子也有 \(j\) 个球给它配对，共 \(j^2\) 种方案。由于这种情况直接消耗了两个（也就是一组）没有配对的球和盒子，所以转移方程长这样：
\[f_{i+1,j-1,k+2j}\gets f_{i,j,k}\times j^2 \]那么问题来了，为什么是 \(k+2j\) 呢？
我们可以理解为：状态中的 \(j\) 有另一种解释，\(1\sim i\) 的这些球有 \(j\) 个要放到编号大于 \(i\) 的盒子里。那么如果把第 \(i\) 组球和盒子处理完了，也就是将前 \(j\) 个球和盒子中的一个配上对了，那么剩下的就要都再往下配对一行，导致总共多出了 \(2j\) 的贡献。
这篇题解对 \(k+2j\) 的解释更加详细。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
using ll=long long;
constexpr int MAXN=55,MOD=1e9+7;
int n,K;
int dp[MAXN][MAXN][MAXN*MAXN];
void add(int&x,int y){
x=x+y>=MOD?x+y-MOD:x+y;
}
int main(){
n=read(),K=read();
if(K&1)return write(0),fw,0;
dp[0][0][0]=1;
for(int i=0;i<n;++i)
for(int j=0;j<=i;++j)
for(int k=0;k<=K;++k){
add(dp[i+1][j][k+2*j],(ll)dp[i][j][k]*(j<<1|1)%MOD);
if(j)add(dp[i+1][j-1][k+2*j],(ll)dp[i][j][k]*j%MOD*j%MOD);
add(dp[i+1][j+1][k+2*j],dp[i][j][k]);
}
write(dp[n][0][K]);
return fw,0;
}