[HAOI2009] 逆序对数列
题目描述
对于一个数列 \(\{a_i\}\)，如果有 \(i<j\) 且 \(a_i>a_j\)，那么我们称 \(a_i\) 与 \(a_j\) 为一对逆序对数。若对于任意一个由 \(1 \sim n\) 自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为 \(k\) 的这样自然数数列到底有多少个？
输入格式
第一行为两个整数n，k。
输出格式
写入一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对10000求余数后的结果。
样例 #1
样例输入 #1
4 1样例输出 #1
3提示
样例说明：
下列3个数列逆序对数都为1；分别是1 2 4 3 ；1 3 2 4 ；2 1 3 4；
测试数据范围
30%的数据 n<=12
100%的数据 n<=1000，k<=1000
解析
设 \(f_{i,j}\) 表示长度为 \(i\)，逆序对数为 \(j\) 的数列的数量
模拟一个新数加入到数列的过程：
假设原数列为 \(a_1,a_2,...a_{n-1}\)，新添加 \(a_n=n\)
因为 \(a_n > a_1,a_2,...a_{n-1}\)，所以当把 \(a_n\) 插入原数列的任意一个空隙里，可以使逆序对数最少增加 \(0\)（放在 \(a_{n-1}\) 之后），最多增加 \(n-1\)（放在 \(a_1\) 之前）
所以，设 \(k\) 为每次新增的逆序对数，则有：
\[f_{i,j} = \sum_{k \le i-1\ \rm{and}\ j-k \ge 0}^{k=0}f_{i-1,j-k} \]时间复杂度 \(O(N^3)\)
观察到上面有 \(f_{i-1,j-k}\) 的形式，所以可以开一个前缀和数组记录 \(\sum_{t \le m}^{t=0}f_{i-1,t}\)，每次用前缀和查询 \(\sum_{l \le j}^{l=j-i+1}f_{i-1,l}\) 即可优化成 \(O(N^2)\)
代码
#include<cstdio>
using namespace std;
const int N=5005,K=5005,M=10000;
int n,m,f[N][K],sum[K];
inline int solve(int l,int r)
{
if(l<0) l=0;
return (sum[r]-sum[l-1])%M;
}
int main()
{
scanf("%d%d",&n,&m);
f[1][0]=1;
for(int i=2;i<=n;i++)
{
sum[0]=1;
for(int j=1;j<=m;j++)
sum[j]=sum[j-1]+f[i-1][j]%M;
for(int j=0;j<=m;j++)
f[i][j]=solve(j-i+1,j)%M;
}
printf("%d\n",f[n][m]%M);
return 0;
}