$$\mathrm{俄罗斯套娃}$$

题目链接：$\mathrm{S}\mathrm{S}\mathrm{L}比赛1475$

题目

输入

输出

样例输入

10 1000

样例输出

3628800

数据范围

思路

这道题用 dp 来做。

就设 $f[i][j]$ 为拿了前 $i$ 个套娃，有 $j$ 个逆序对有多少方案。
我们可以发现，当拿第 $i$ 个套娃的时候，无论前面的怎么放，增加的逆序对数量只跟它插入的位置有关。（因为这个套娃一定比摆好的大）套娃最少可不增加逆序对数，最多可以增加 $i-1$ 个逆序对。我们可以拿这一点来 dp 。

但是，这样还是会超时，我们就发现其实我们枚举套娃插入的位置的时候，是不断递增的，就是说我们可以用前缀和把枚举套娃插入的位置这个循环代替。不过当逆序对个数 $j$ 超过了套娃的数量 $i$ ，它就会慢慢减少，减少的就是 $f[i-1][j-i]$ 。

但是我们发现会超内存，那我们可以发现 $f[i][j]$ 只会被 $f[i-1][k]$ 影响（ $k$ 表示常数），那我们就可以用滚动数组储存 $f$ 。

代码

#include<cstdio>
#define ll long long
#define mo 10000000007

using namespace std;

ll n, K, f[3][3001], ans, ways;

int main() {
	scanf("%lld %lld", &n, &K);//读入
	
	f[1][0] = 1;//初始化
	for (ll i = 2; i <= n; i++) {
		ways = 0;
		for (ll j = 0; j <= K; j++) {
			if (i <= j) ways = (ways - f[(i - 1) & 1][j - i] + mo) % mo;//变回小
			ways = (ways + f[(i - 1) & 1][j]) % mo;//前缀和
			f[i & 1][j] = ways;//记录
		}
	}
	
	for (ll i = 0; i <= K; i++)
		ans = (ans + f[n & 1][i]) % mo;//统计答案
	
	printf("%lld", ans);//输出
	
	return 0;
}