#C241016C. [HAOI2009] 逆序对数列

标签（Label）

• 动态规划

网址（Website）

P2513 [HAOI2009] 逆序对数列 - 洛谷

「HAOI2009」逆序对数列 - Super

题解（Solution）

（不是哥们儿，这东西你是真的不会啊？）

由极其容易地推出了状态表达式：$f_{i,j}$ 表示到了第 $i$ 个数，此时逆序对个数为 $j$ 。

然后脑瓜蹦子又卡壳了——怎么推？

考虑到逆序对的性质，我们如果每次加的数都比之前的大，当前的转移就不会受前面的数的影响，而每次加的数最后一定能构成满足条件的序列。

改一下方程式的定义：把第 $i$ 个数改成放从 $1\sim n$ 放数字，当前放到了第 $i$ 个，然后直接前缀和就完了。

发现对于 $f_{i,j}$ ，放下第 $i$ 个数只能产生最多 $i-1$ 个逆序对，因此只能从 $f_{i-1,k}(k\in[j-i+1,j])$ 这些状态里面转移，得解。

时间复杂度： $O(n^2)$ 。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1005;
const int mod = 10000;
bool ST;

int f[N][N];
int n,k;

inline int cal(int i,int l,int r){
	if(l<0) return f[i][r];
	else return (f[i][r] - f[i][l-1] + mod*2)%mod;
}

void solve(){
	n = rd(), k = rd();
	For(j,0,k) f[1][j] = 1;
	For(i,2,n){
		For(j,0,k) f[i][j] = cal(i-1, j-i+1, j);
		if(i!=n) For(j,1,k) (f[i][j] += f[i][j-1])%=mod;
	}printf("%lld\n", f[n][k]%mod);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1, Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}