记录编号	598080	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]逆序对数列	最终得分	100
用户昵称	djyqjy	是否通过	通过
代码语言	C++	运行时间	0.068 s
提交时间	2025-01-05 09:45:24	内存使用	4.76 MiB

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int f=1,num=0;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
	return num*f;
}
const int N=1010,MOD=10000;
int dp[N][N];
int n,k;
int sum;
int main()
{
	freopen("permut.in","r",stdin);
	freopen("permut.out","w",stdout);
	n=read();k=read();
	dp[1][0]=1;
	for(int i=2;i<=n;i++)
	{
		sum=0;
	    for(int j=0;j<=k;j++)
	    {
	    	sum=((sum+dp[i-1][j]-(i<=j?dp[i-1][j-i]:0))%MOD+MOD)%MOD;
	    	dp[i][j]=sum;
		}
	}
	printf("%d",dp[n][k]);
	return 0;
}