排队

题目大意

*小花所在的班有 n名同学（任何两位同学身高不相同），正准备排成一列纵队，但他们不想按身高从矮到高排，那样太单调，太没个性。
*他们希望恰好有 k对同学是高的在前，矮的在后，其余都是矮的在前，高的在后。如当 n=5,k=3 时，假设5 人从矮到高分别标为 1,2,3,4,5，则 (1,5,2,3,4）,(2,3,1,5,4),(3,1,4,2,5)都是可行的排法。
*小花想知道总共有多少种可行排法。

输入格式

一行两个整数 n 和 k，意义见问题描述。

输出格式

输出一个整数，表示可行排法数。由于结果可能很大，请输出排法数 mod 1799999 的值。

样例

样例输入

5 3

样例输出

算法分析：

这nm是dp？
这nm还真是dp（以为是数论直接跳了……）
这个是可以用递推做出来的用f[i][j]表示前i个人有j对逆序对（不懂的去百度吧）
初始化f[i][0] = 1（即正好是顺序排列）
然后我们去推第i个数想象如果第i个数最大放在最后面就一个不会加放在倒数第二个呢就会加一个依次类推……
然后就有了动态转移方程了f[i][j] = f[i-1][j] + f[i-1][j-1] + ... + f[i-1][j-i+1]
用j-1代换j 则： f[i][j-1] = f[i-1][j-1] + f[i-1][j-2] + ... + f[i-1][j-i]
用上面的式子减下面的式子得：f[i][j] = f[i][j-1] + f[i-1][j] - f[i-1][j-i]
然后就可以码代码啦

代码展示

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105,mod = 1799999;

int n,k,sum;
ll f[maxn][maxn*maxn];

int main(){
	scanf("%d%d",&n,&k);
	for(int i = 1;i <= n;++i)f[i][0] = 1;
	for(int i = 1;i <= n;++i){
		sum += i - 1;//优化 前i个最多出现sum个逆序对
		for(int j = 1;j <= k;++j){
			if(j > sum)break;
			f[i][j] = (f[i][j-1] + f[i-1][j]) % mod;
			if(i <= j)
				f[i][j] = (f[i][j] - f[i-1][j-i] + mod) % mod;//防止相减出现负数
		}
	}
	printf("%lld
",f[n][k] % mod);
	return 0;
}

如初见与初见