[BZOJ2431][HAOI2009]逆序对数列(DP)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 5 using namespace std;
 6 
 7 const int N=1010,mod=10000;
 8 int n,k,f[N][N],g[N][N];
 9 
10 int main(){
11     scanf("%d%d",&n,&k);
12     f[1][0]=1; rep(i,0,k) g[1][i]=1;
13     rep(i,2,n){
14         f[i][0]=g[i][0]=1;
15         rep(j,1,k){
16             f[i][j]=(g[i-1][j]-((j-i>=0)?g[i-1][j-i]:0)+mod)%mod;
17             g[i][j]=(g[i][j-1]+f[i][j])%mod;
18         }
19     }
20     printf("%d\n",f[n][k]);
21     return 0;
22 }