题解：P10254 口吃

· · 题解

想办法把一个排列的权值往逆序对数量上靠。

可以拆式子

\begin{aligned} \sum_i i\times a_i &= \sum_i a_i\times(1+\sum_{j<i}[a_j<a_i]+\sum_{j<i}[a_j>a_i]) \\ &= \sum_i a_i + \sum_{j<i}a_i\times [a_j<a_i]+\sum_{j<i}a_i\times[a_j>a_i] \end{aligned}

发现这三项都可以 DP 做。

设 h_{i,j} 表示填了 i 个数，有 j 个逆序对的方案数，f_{i,j} 为填 [1,i] 的数，有 j 个逆序对的所有排列对应的第二个式子的权值和，g_{i,j} 为填 [i,n] 的数，有 j 个逆序对的所有排列对应的第三个式子的权值和。

对于 h 和 f 的转移，考虑每次插入最大值。枚举 k 为新增的逆序对数量，有转移：

h_{i,j}\gets h_{i-1,j-k} f_{i,j}\gets f_{i-1,j-k}+h_{i-1,j-k}\times (i-1-k) \times i

对于 g 的转移，考虑每次插入最小值。枚举 k 为新增的逆序对数量，有转移：

g_{i,j}\gets g_{i+1,j-k}+h_{n-i,j-k}\times k \times i

答案为：

\frac{n(n-1)}{2}\times h_{n,k}+f_{n,k}+g_{1,k}

时间复杂度 \Theta(n^2k)。

注：代码中为了方便，转移 g 时，将 h_{i,j} 的定义改为填了 n-i+1 个数，有 j 个逆序对的方案数。

::::info[代码]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
const ll inv2 = 499122177;
void Add(int &x, int y){(x += y) >= mod ? x -= mod : 0;}
int add(int x, int y){Add(x, y); return x;}
const int kN = 301;
int n, k, f[2][kN * kN], g[2][kN * kN],  h[2][kN * kN];
signed main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  h[1][0] = 1;
  for(int i = 2; i <= n; i++){
    memcpy(f[0], f[1], sizeof(f[1]));
    memcpy(h[0], h[1], sizeof(h[1]));
    memset(f[1], 0, sizeof(f[1]));
    memset(h[1], 0, sizeof(h[1]));
    for(int j = 0; j <= i * (i - 1) / 2; j++){
      for(int k = 0; k < i; k++){
        if(j >= k){
          Add(h[1][j], h[0][j - k]);
          Add(f[1][j], f[0][j - k]);
          Add(f[1][j], h[0][j - k] * 1ll * (i - 1 - k) % mod * i % mod);
        }
      }
    }
  }
  int ans = 1ll * n * (n + 1) % mod * inv2 % mod * h[1][k] % mod;
  Add(ans, f[1][k]);
  memset(h[1], 0, sizeof(h[1]));
  h[1][0] = 1;
  for(int i = n - 1; i >= 1; i--){
    memcpy(g[0], g[1], sizeof(g[1]));
    memcpy(h[0], h[1], sizeof(h[1]));
    memset(g[1], 0, sizeof(g[1]));
    memset(h[1], 0, sizeof(h[1]));
    for(int j = 0; j <= (n - i) * (n - i + 1) / 2; j++){
      for(int k = 0; k <= n - i; k++){
        if(j >= k){
          Add(h[1][j], h[0][j - k]);
          Add(g[1][j], g[0][j - k]);
          Add(g[1][j], h[0][j - k] * 1ll * k % mod * i % mod);
        }
      }
    }
  }
  Add(ans, g[1][k]);
  cout << ans << '\n';
  return 0;
}

::::

发现 h、f、g 的转移都可以直接用前缀和优化。

时间复杂度 \Theta(nk)。

::::info[代码]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
const ll inv2 = 499122177;
void Add(int &x, int y){(x += y) >= mod ? x -= mod : 0;}
int add(int x, int y){Add(x, y); return x;}
const int kN = 301;
int n, k, f[2][kN * kN], g[2][kN * kN],  h[2][kN * kN];
int sh[kN * kN], sf[kN * kN], sg[kN * kN], sh2[kN * kN], sg2[kN * kN], sh3[kN * kN];
signed main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  h[1][0] = 1;
  for(int i = 0; i <= n * (n - 1) / 2; i++) sh[i] = sh2[i] = 1;
  for(int i = 2; i <= n; i++){
    memcpy(f[0], f[1], sizeof(f[1]));
    memcpy(h[0], h[1], sizeof(h[1]));
    memset(f[1], 0, sizeof(f[1]));
    memset(h[1], 0, sizeof(h[1]));
    for(int j = 0; j <= i * (i - 1) / 2; j++){
      int l = min(j, i - 1);
      f[1][j] = (sh2[j] - (j > l ? sh2[j - l - 1] : 0) + mod) % mod;
      Add(f[1][j], mod - (sh[j] - (j > l ? sh[j - l - 1] : 0) + mod) % mod * 1ll * j % mod);
      f[1][j] = f[1][j] * 1ll * i % mod;
      Add(h[1][j], (sh[j] - (j > l ? sh[j - l - 1] : 0) + mod) % mod);
      Add(f[1][j], (sf[j] - (j > l ? sf[j - l - 1] : 0) + mod) % mod);
    }
    sh[0] = h[1][0], sh2[0] = h[1][0] * 1ll * i % mod, sf[0] = f[1][0];
    for(int j = 1; j <= n * (n - 1) / 2; j++){
      sh[j] = add(sh[j - 1], h[1][j]);
      sh2[j] = add(sh2[j - 1], h[1][j] * 1ll * (i + j) % mod);
      sf[j] = add(sf[j - 1], f[1][j]);
    }
  }
  int ans = 1ll * n * (n + 1) % mod * inv2 % mod * h[1][k] % mod;
  Add(ans, f[1][k]);
  memset(h[1], 0, sizeof(h[1]));
  h[1][0] = 1;
  for(int i = 0; i <= n * (n - 1) / 2; i++) sh[i] = 1;
  for(int i = n - 1; i >= 1; i--){
    memcpy(g[0], g[1], sizeof(g[1]));
    memcpy(h[0], h[1], sizeof(h[1]));
    memset(g[1], 0, sizeof(g[1]));
    memset(h[1], 0, sizeof(h[1]));
    for(int j = 0; j <= (n - i) * (n - i + 1) / 2; j++){
      int l = min(j, n - i);
      g[1][j] = mod - (sh3[j] - (j > l ? sh3[j - l - 1] : 0) + mod) % mod;
      Add(g[1][j], (sh[j] - (j > l ? sh[j - l - 1] : 0) + mod) % mod * 1ll * j % mod);
      g[1][j] = g[1][j] * 1ll * i % mod;
      Add(h[1][j], (sh[j] - (j > l ? sh[j - l - 1] : 0) + mod) % mod);
      Add(g[1][j], (sg[j] - (j > l ? sg[j - l - 1] : 0) + mod) % mod);
    }
    sh[0] = h[1][0], sh3[0] = 0, sg[0] = g[1][0];
    for(int j = 1; j <= n * (n - 1) / 2; j++){
      sh[j] = add(sh[j - 1], h[1][j]);
      sh3[j] = add(sh3[j - 1], h[1][j] * 1ll * j % mod);
      sg[j] = add(sg[j - 1], g[1][j]);
    }
  }
  Add(ans, g[1][k]);
  cout << ans << '\n';
  return 0;
}

::::