BZOJ2431 [HAOI2009] 逆序对数列

2018 年 03 月 14 日发布.

Description

求$1$到$n$的排列中逆序对数为$k$的排列个数。$n,k\leqslant1000$。

Solution

dp。考虑如果第一个数为$t$，那么会产生$t-1$个逆序对；剩下的相当于一个$n-1$的排列。所以 $$ f_{n,k}=\sum_{i=0}^{n-1}f_{n-1,k-i} $$ 代码中强行前缀和优化qwq。

Code

#include <cstdio>
const int N = 1050;
const int mod = 10000;
int f[N][N];
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  f[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    f[i][0] = 1;
    for (int j = 1; j <= k; ++j) {
      f[i][j] = f[i][j - 1] + f[i - 1][j];
      if (j >= i) f[i][j] -= f[i - 1][j - i];
      f[i][j] %= mod;
    }
  }
  printf("%d\n", (f[n][k] + mod) % mod);
  return 0;
}