记录编号	384943	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]逆序对数列	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.058 s
提交时间	2017-03-19 19:51:46	内存使用	15.88 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define is_num(tmp) (tmp<='9' and tmp>='0')
#define MOD 10000
#define MAXN 1010

inline int in(void){
	char tmp=getchar();
	int res=0, f=1;
	while(!(is_num(tmp) || tmp=='-'))tmp=getchar();
	if(tmp=='-')f=-1, tmp=getchar();
	while(is_num(tmp))
		res=(res<<1)+(res<<3)+(tmp^48),
		tmp=getchar();
	return res*f;
}

long long f[MAXN][MAXN], g[MAXN][MAXN];
int N, K;
int main(){
#ifndef LOCAL
	freopen("permut.in", "r", stdin);
	freopen("permut.out", "w", stdout);
#endif
	
	N=in(), K=in();
	
	for(int i=0; i<=K; ++i)g[0][i]=1;
	
	for(int i=1; i<=N; ++i){
		for(int j=0; j<=K; ++j){
			if(j>=i)f[i][j]=(g[i-1][j]-g[i-1][j-i]+MOD)%MOD;
			  else f[i][j]=g[i-1][j]%MOD;
			if(j)g[i][j]=(g[i][j-1]+f[i][j])%MOD;
			  else g[i][j]=f[i][j]%MOD;
		}
	}
	printf("%d", f[N][K]);
	
	return 0;
}