牛客挑战赛46 C

题目链接：

排列

考虑\(dp\)，我们思考如何设计状态

将第i个数插入i-1个数中，我们考虑会新增多少个超级逆序对

假设将\(i\)插入后\(i\)的位置为\(l\)，\(i-1\)的原来的位置为\(l2\)

如果\(l2>=l\) 我们会新产生\(i-l-1\)个逆序对

否则\(l2<l\) 我们会新产生\(i-l\)个逆序对

设j为逆序对的个数，我们可以得到如下的状态转移方程

\(dp[i][j][l]+=dp[i-1][j-i+l+1][l2]\)如果\(l2>=l\)

否则\(dp[i][j][l]+=dp[i-1][j-i+l][l2]\)如果\(l2<l\)

容易发现\(l2\)是线性的，我们可以通过前缀和优化降低时间复杂度

同时可通过设计\(las\)数组舍弃\(i\)，降低空间复杂度

总时间复杂度为\(O(n^3)\),空间复杂度为\(O(n^2)\)

代码：

#include <bits/stdc++.h>
#define mod 998244353
#define LL long long
using namespace std;
int n, k;
const int N = 511;
LL dp[N][N], sum[N][N], las[N][N];
 
LL ksm(LL a,LL b)
{
	LL res = 1;
	while(b) 
	{
		if(b & 1) res = res * a % mod;
		a = a * a % mod; b >>= 1;
	} 
	return res;
}

int main()
{
	scanf("%d%d",&n,&k);
	dp[0][1] = 1;las[0][1] = 1;
	for(int i = 2;i <= n; i++)
	{
		memset(dp,0,sizeof(dp));
		for(int j = 0;j <= k; j++)
		for(int l = 1;l <= i; l++)
		    sum[j][l] = sum[j][l - 1] + las[j][l];
	    for(int j = 0;j <= k; j++)
	    for(int l = 1;l <= i; l++)
	    {
        	if(j - i + l + 1 >= 0) dp[j][l] = (dp[j][l] + sum[j - i + l + 1][i] - sum[j - i + l + 1][l - 1]) % mod;
			if(j - i + l >= 0) dp[j][l] = (dp[j][l] + sum[j - i + l][l - 1]) % mod;
	    }
	    for(int j = 0;j <= k; j++)
	        for(int l = 1;l <= n; l++)
	            las[j][l] = dp[j][l];
    }
	LL ans = 0;
	for(int i = 1;i <= n; i++) ans = (ans + dp[k][i]) % mod;
	printf("%lld\n",ksm(ans,mod - 2));
}