【abc134F】Permutation Oddness

Source

abc134F

Hint

请先思考后再展开

$\sum |w(i)-i|=2\sum_{w(i)>i} w(i)-i$
考虑怎么把费用拆分计算
首先思路是先考虑怎么设计一个dp能支持把阶乘拆分,最后通过这个dp成功算出阶乘,然后再加入第三维去计算
注意到位置和上面的数地位平等,所以应当看做是两个递增的序列然后连线,上面位置下面数

Solution

这题让lxj教了我很久才会……很久没有这种体验了

请先思考后再展开

为了方便方案数的计算,不妨规定将系数放在右边计算,特判竖线(就是上i连下i,因为两个都是最右的嘛)
(因为没有题解我们是看代码的,然后没有上面这句话理解起来非常操蛋,以为把阶乘拆成了平方,其实只是恰好要算两条)
然后状态设计也很奇妙,主要是f(i,j),表示从左到右处理了2i个点,然后两端都在i内的有j对
转移就是考虑当前的两个新点(上i和下i),然后讨论连接他们的节点是朝哪个方向的来转移(此时考虑的都是斜线而不是竖线)
定义【左+右】表示上面连向下面i左边,下面连向上面i右边(与【右+左】简称【1左1右】)

1
2
3
4
5
6
for(int i=0;i<n;i++) for(int j=0;j<=i;j++) if(f[i][j])
{
f[i+1][j+1]+=f[i][j]*( (i-j)*2+1 );//【1左1右】、【竖线】转移系数都相同
f[i+1][j+2]+=f[i][j]*(i-j)*(i-j);//【左+左】
f[i+1][j]+=f[i][j];//【右+右】
}

填充一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
ll f[N][N][N*N*2];
#define F(a,b,c) f[a][b][c+N*N]
void main()
{
int n=qread(),K=qread();F(0,0,0)=1;
for(int i=0;i<n;i++) for(int j=0;j<=i;j++) for(int k=-2500;k<=2500;k++) if(F(i,j,k))
{
add(F(i+1,j+1,k),F(i,j,k)*( (i-j)*2+1 )%MOD);//【1左1右】、【竖线】
add(F(i+1,j+2,k+i),F(i,j,k)*(i-j)%MOD*(i-j)%MOD);//左+左
add(F(i+1,j,k-i),F(i,j,k));//右+右
}
if(K&1) puts("0"); else write( F(n,n,K/2) );
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/3455.html
转载请注明出处,谢谢!