记录编号	598076	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]逆序对数列	最终得分	100
用户昵称	袁书杰	是否通过	通过
代码语言	C++	运行时间	0.091 s
提交时间	2025-01-04 18:10:05	内存使用	7.70 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[1005][1005],n,k,s[1005][1005];
signed main() {
	freopen("permut.in","r",stdin);
	freopen("permut.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	dp[0][0]=1;
	for(int i=0; i<=k; i++) {
		s[0][i]=1;
	}
	for(int i=1; i<=n; i++) {
		for(int j=0; j<=k; j++) {
			dp[i][j]=s[i-1][j];
			if(j>=i){
				dp[i][j]+=10000;
				dp[i][j]-=s[i-1][j-i];
			}
			dp[i][j]%=10000;
			if(j!=0) {
				s[i][j]=s[i][j-1];
			}
			s[i][j]+=dp[i][j];
			s[i][j]%=10000;
		}
	}
	cout<<dp[n][k]%10000;
	return 0;
}