NC19976. [HAOI2009]逆序对数列
描述
输入描述
第一行为两个整数n，k。
输出描述
写入一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对10000求余数后的结果。
示例1
输入:
4 1
输出:
3
说明:
样例说明：C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 7672K, 提交时间: 2020-08-15 12:47:58
#include<bits/stdc++.h>
using namespace std;
const int p=1e4;
int f[1010][1010],n,k,sum[1010][1010];
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
f[i][0]=1;sum[i][0]=1;
for(int j=1;j<=k;j++)
{
f[i][j]=(sum[i-1][j]-sum[i-1][j-min(i-1,j)-1]+p)%p;
sum[i][j]=(sum[i][j-1]+f[i][j])%p;
}
}
printf("%d\n",f[n][k]);
}