排列

NC212475. 排列

描述

牛牛正在跟牛妹玩游戏。

牛牛手里捧着 n 个数 $1,2,\dots ,n$ ，并按这一些数某种顺序排成一个数列。具体地，如果数列是 $\{ a_1,a_2,\dots\,a_n\}$ ，则 $\{ a_1,a_2,\dots\,a_n\} = \{ 1, 2, \dots n\}$ 。

牛妹很想知道牛牛手里捧着的数列是什么。但调皮的牛牛只告诉她这个数列的超级逆序对为 k 。

牛妹会随便猜一个符合牛牛要求的数列，她想知道猜对这个数列的概率为多少，答案对 998244353 取模。

超级逆序对的定义：满足 i<j 且 $a_i>a_j+1$ 的二元组 (i,j) 。

例如：对于数列 a={ 2,4,5,3,1} ，二元组 (3,4) , (3,5) 均是超级逆序对。

输入描述

读入 n 和 k

输出描述

输出概率。

示例1

输入:

1 0

输出:

示例2

输入:

100 100

输出:

545068381

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 617ms, 内存消耗: 249896K, 提交时间: 2021-06-18 16:52:46

#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
int f[505][505][505];
int n,k;

int ksm(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod,y/=2;
	}
	return res;
}

int main(){
	scanf("%d %d",&n,&k);
	f[1][1][0]=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			for(int l=0;l<=k;l++){
				if(l+i-j<=k) (f[i][j][l+i-j]+=f[i-1][j-1][l])%=mod;
				if(l+i-j-1<=k) (f[i][j][l+i-j-1]+=(f[i-1][i-1][l]+mod-f[i-1][j-1][l])%mod)%=mod;
			}
		}
		for(int l=0;l<=k;l++){
			for(int j=2;j<=i;j++) (f[i][j][l]+=f[i][j-1][l])%=mod; 
		}
	}
	printf("%d\n",ksm(f[n][n][k],mod-2));

	return 0;
}