对序逆

NC222133. 对序逆

描述

定义 $a$ 序列两位置 $i,j$ 是逆序对的条件是 $i<j$ 且 $a_i>a_j$ 。

小 $\mathcal O$ 喜欢魔改各种各样的排序，现在他乱搞出一种 $O(n^2)$ 求逆序对的新方法：

小 $\mathcal O$ 保证 $a_i$ 是整数且 $a_i\in[1,m]$ 。他想知道这 $m^n$ 种情况中有几种情况求出来的逆序对是正确的。

输入描述

两个整数 。

输出描述

一个整数表示答案，对  取模。

示例1

输入:

2 2

输出:

示例2

输入:

3 2

输出:

示例3

输入:

8 8

输出:

原站题解

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

C++ 解法, 执行用时: 384ms, 内存消耗: 448K, 提交时间: 2021-06-05 21:54:08

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

const int mod=998244353;
int i,j,n,m,DP[2][10005];
int main()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)DP[1][i]=i;
    for(i=2;i<=n;i++)
    	for(j=1;j<=m;j++)DP[i&1][j]=(DP[i&1][j-1]+DP[(i-1)&1][j]+(long long)DP[(i-1)&1][j-1]*(i-1))%mod;
	printf("%d\n",DP[n&1][m]);
    return 0;
}

上一题

下一题

详情