Bzoj 2431: [HAOI2009]逆序对数列

原题网址：http://www.lydsy.com/JudgeOnline/problem.php?id=2431 用 f[i][j] 表示前 i 个数字为止产生j个逆序对的方案数，显然第 i 个数放进去会产生0~ i−1 个逆序对，用前缀和优化转移即可。

#include<bits/stdc++.h> const int N = 1005; const int K = 1005; const int Mod = 10000; int n,k,f[N][K],sum[N][K]; int main(){ scanf("%d%d",&n,&k); f[1][0] = 1; for (int i=0; i<=k; i++) sum[1][i] = 1; for (int i=2; i<=n; i++) for (int j=0; j<=k; j++){ if (j - i >= 0) f[i][j] = (sum[i - 1][j] - sum[i - 1][j - i] + Mod) % Mod; else f[i][j] = sum[i - 1][j]; if (j > 0) sum[i][j] = (sum[i][j - 1] + f[i][j]) % Mod; else sum[i][j] = f[i][j]; } printf("%d\n",f[n][k]); return 0; }