SP64 [PERMUT1 - Permutations] - 粉粉何所似？

~~我会告诉你这是三倍经验题吗。。。~~

做完这道你可以去做P1521 求逆序对和[P2513 [HAOI2009]逆序对数列](https://www.luogu.org/problemnew/show/P2513)

~~但是我并不确定我的代码在P2513不会TLE~~

题面

在这道题中，你会发现你逆序对的个数只和相对大小有关！！

然后就可以建立DP模型： $dp[i][j]$ 表示 $i$ 个不同的数的所有排列中，逆序对数量为 $j$ 的排列个数。初始边界为 $dp[1][0]=1$ 。

关于 $dp$ 方程：当有 $i-1$ 个数时，有 $j-1$ 个逆序对时，添加第 $i$ 个数，必有一个位置刚好使逆序对数 $+1$ ，即可转移到 $dp[i][j]$ 。同理 $j-2,j-3……j-(i-1)$ ，因为只有 $i-1$ 个数，所以最多到 $i-1$ ，当然也可能不增加逆序对。

Code：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k,w;
int dp[1001][1001];
int main(){
    scanf("%d",&w);
    while (w--){
        memset(dp,0,sizeof (dp));
        scanf("%d%d",&n,&k);
        dp[1][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=k;j++){
                for(int l=0;l<i;l++){
                    if(j>=l)
                        dp[i][j]+=dp[i-1][j-l];
                }
            }
        }
        printf("%d\n",dp[n][k]);
    }
    return 0;
}