题目描述
对于一个数列 {}，如果有 i<j 且
，那么我们称与
为一对逆序对数。若对于任意一个由1∼n 自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为 k 的这样自然数数列到底有多少个？
输入格式
第一行为两个整数n，k。
输出格式
写入一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对10000求余数后的结果。
样例
输入数据 1
4 1
输出数据 1
3
提示
------------------------------------------------------
分析：
从题目大意来看，这是一个排列组合问题，我们用DP来解决。
排列组合的话，当前状态与前面的状态都是有关联的，自然想到DP思想。
我们用DP[i][j]来表示i个数列通过排序产生K个逆序对的排列总数。
例如P[5][4] 表示有5个自然数，所有的排列中产生4个逆序对的排列的总和。
假设A5是最大的数。
那么在这5个数中，A5能放的位置有哪些呢？是不是只有下面几种情况。
(#代表其他四个数)
第一种：####A5 将A5放在最后
第二种：###A5# 放在倒数第二
第三种：##A5## 放在倒数第三
第四种：#A5### 放在倒数第四
第五种：A5#### 放在第一个位置
5个数的话，A5的位置是不是只有上面几种情况。
接下来在每种情况下求出4个逆序对排列的数量，这把他们全部累积就是P[5][4]
第一种情况：因为A5在最后位置，所以A5的位置不会影响前面四个数排列产生的逆序对数量。所以4个逆序对的排列数就是前面四个数排列来产生，即P[4][4]
第二种情况：因为A5在倒数第二，所以A5#一定是一个逆序对，因为求的是4个逆序对，那么剩余的4个数必须产生3个逆序对，产生这3个逆序对的排列数是不是P[4][3]呢，P[4][3]就是第二种情况下排列数。
第三种情况：因为A5在倒数第三，所以A5##一定可以产生2个逆序对，因为求的是4个逆序对，那么剩余的4个数必须产生2个逆序对，产生这2个逆序对的排列数是不是P[4][2]呢，P[4][2]就是第三种情况下排列数。
第四种情况：因为A5在倒数第四，所以A5###一定可以产生3个逆序对，因为求的是4个逆序对，那么剩余的4个数必须产生1个逆序对，产生这1个逆序对的排列数是不是P[4][1]呢，P[4][1]就是第四种情况下排列数。
第五种情况：因为A5在第一位置，所以A5####一定可以产生4个逆序对，因为求的是4个逆序对，那么剩余的4个数必须产生0个逆序对，产生这0个逆序对的排列数是不是P[4][0]呢，P[4][0]就是第五种情况下排列数。
所以P[5][4]就等于上面四种情况下的排列和=P[4][4]+P[4][3]+P[4][2]+P[4][1]+P[4][0]
接下来，我们再扩展思考一下，如果是i个数，那么第i个数Ai，是不是可以分别放在下面这些位置：i，i-1，...，2，1。对于每个位置因为Ai产生的逆序对数量为：0，1，...，i-2，i-1。
如果Ai A1 A2 … Ai-2 Ai-1（Ai放在第一个位置），那么Ai与后面i-1个数都可以构成逆序对，也就总共有i-1个逆序对。如下
Ai与A1
Ai与A2
...
Ai与Ai-2
Ai与Ai-1
题目要求为i个数排列组合，产生k个逆序对的排列数。
那么Ai如果在最后，产生逆序对0个，那么余下的i-1个数就要产生K个逆序对才行 排列数：P[i-1][k]
那么Ai如果在倒数第二，产生逆序对1个，那么余下的i-1个数就要产生K-1个逆序对才行 排列数：P[i-1][k-1]
...
以此类推
那么Ai如果在第一个位置，产生逆序对i-1个，那么余下的i-1个数就要产生K-(i-1）个逆序对才行 排列数：P[i-1][k-(i-1)]
那么总的排列数P[i][k]=P[i-1][k]+P[i-1][k-1]+...+P[i-1][k-(i-2)]+P[i-1][k-(i-1)] 方程①
如果用k-1代替上面k的话，上面公式可以变为↓
P[i][k-1]=P[i-1][k-1]+P[i-1][k-1]+...+P[i-1][k-1-(i-2)]+P[i-1][k-1-(i-1)] 方程②
方程①-方程② 可以得到简化的通项公式
P[i][k]=P[i-1][k]+P[i][k-1]-P[i-1][k-i]
有了这个通项公式，是不是就简单化了。
但是要注意，k<i的时候 P[i-1][k-i] 是无意义的。所以需要用if做个判断
因为这是反复迭代的问题，我们需要知道终止时的末项值才行，就是这个P[i][0]，对于一个序列通过排序得到0个逆序对，一定只有一种排序方法,就是递增。所以P[i][0]=1。
Code
#include<bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) dp[i][0]=1;
for (int i=2;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
dp[i][j]=(dp[i][j-1]+dp[i-1][j])%10000;
if(j>=i)
dp[i][j]=(dp[i][j]-dp[i-1][j-i]+10000)%10000;
}
}
cout<<dp[n][k];
}补充说明：
为什么(dp[i][j]-dp[i-1][j-i]+10000)，需要加10000呢？思考过吗？
因为(dp[i][j-1]+dp[i-1][j])%10000取模之后会将原本比较大的数变的比较小了，例如原本是100057的数变成了57，此时-dp[i-1][j-i]是57~9999的话，(dp[i][j-1]+dp[i-1][j])就变成了负数，为了防止出现负数，我们还是要用100057去减才能得到真正的数值。