题解 - QOJ 7766 栞

简述题意

对于 $1\sim n$ 的排列 $p$，定义 $f(p)$ 为把 $p$ 划分为 $k$ 连续段后每段分别排序、其中所有划分方法中所可能达成的字典序最小的排列。给定 $f(p),k$，数 $p$ 的个数。$1\le k\le n\le 500$。

解析

令 $f(p)=q$。

刻画 $f$ 函数的过程

既然求字典序最小的排列，首先要 $q_1$ 最小。$q_1=\min_{1\le i\le n-k+1}p_i$。（这个上界是因为剩余的 $k-1$ 段非空）

接着要 $q_2$ 最小，就是把 $q_1$ 屏蔽掉后的最小值。

逐位考虑 $q_i$。以第 $i$ 个数为止分段的条件是：$q_1\sim q_i$ 恰好落在 $p$ 的 $1\sim i$ 位。

在前面能分段就分段，后面部分段数变少，字典序不增。而且既然已经分段，说明 $a_{i+1}\sim a_{n-k+1}$ 都大于 $a_1\sim a_i$，所以也不会变劣。综上可说明此刻画正确性。

部分分：$q_i=i$

则 $p$ 可被划分为至少 $k$ 段，其中每段 $p_l\sim p_r$ 排序后恰好为 $l\sim r$。（即题意）

考虑记 $f_{i,j}$ 为满足这样条件的 $i$ 阶排列个数：它最多刚好可以被划分成 $j$ 段，使每段 $p_l\sim p_r$ 排序后恰好为 $l\sim r$。

对于 $f_{i,1}$ 的计算，方法多样，其中一种是考虑任意 $i-1$ 阶排列的第一个 $x$ 满足 $p_1\sim p_x$ 排序后恰好为 $1\sim x$。要在值域中插入一个数使得 $j=1$，则必有 $p'_i<p'_x$。所以有 $f_{i,1}=\sum_{1\le x\le i-1}f_{x,1}x(i-x-1)!$。

对于其他 $f_{i,j}$，直接 $f_{i,j}=\sum_{1\le x\le j}f_{x,1}f_{i-x,j-1}$ 即可。（也就是生成函数卷积）

答案则为 $\sum_{k\le i\le n}f_{n,i}$。

一般的 $q$

由上文对 $f$ 函数过程的刻画，可知一旦选中一个 $p_{n-k+1}$，这一段以后每一段长度只能为 $1$。只要没有选中，由于 $p_1\sim p_{n-k}$ 总是在 $\min$ 备选范围里面，所以假设选中的是 $t=n-k$，则有 $\forall 2\le i<t,p_{i-1}<p_i$。然而选完 $t$ 之后，出于同样的原因，仍有 $\forall i\ge t,p_i<p_{i+1}$，并且 $p_{t-1}<p_{t+1}$（在对应元素存在的前提下）。然而不保证 $p_{t-1}<p_t$。

所以第一个出现 $p_{i-1}<p_i$ 的 $i$ 只能是 $t$（如果存在）。于是我们找到 $t'$（如果存在），它是 $t$ 之后的第一个满足 $p_{t'-1}>p_t$ 的位置，这个位置开始每一段长度只能为 $1$。换言之，$[t,t')$ 是最后一段长度可能不为 $1$ 的分段，而且这必须是一段。

整理一下，整个序列应该形如这样：$[1,t)$ 是一个递增序列，被分成若干段；$[t,t')$ 是一个递增序列，若它长度不为 $1$ 则必有 $p_{t-1}<p_{t+1}$，并且这一区间独立成段；$[t',n]$ 是若干长度为 $1$ 的段。

所以我们找到 $t$（在非部分分情况下必然存在）后，枚举每个 $t'$，对应的贡献就是 $f_{t,k-(n-t')}(t'-t-1)!$（$[t,t')$ 可以任意排列，$[1,t)$ 如部分分所示），求和即可。

代码

代码中下标从 $0$ 开始，并且有若干命名和操作与公式等效而不同名。

#include <bits/stdc++.h>
using namespace std;

const int MXN = 505;
const int DVS = 998244353;
int N, K, arr[MXN], cnt[MXN][MXN], Pt, ans;
bool type;
int main() {
  cin >> N >> K;
  for (int i(0); i != N; ++i) cin >> arr[i], --arr[i];
  for (int i(1); i != N; ++i) {
    if (arr[i] < arr[i - 1]) {
      Pt = i + 1;
      while (Pt != N && arr[Pt] > max(arr[Pt - 2], arr[Pt - 1])) ++Pt;
      type = 1;
      K -= N - Pt + 1;
      N = i;
      break;
    }
  }
  if (K <= 0) {
    cout << 0 << endl;
    return 0;
  }
  cnt[1][1] = 1;
  for (int i(2); i <= N; ++i) {
    for (int j(i - 1), f(1); j >= 1; f = f * 1LL * (i - j--) % DVS) {
      cnt[i][1] = (cnt[i][1] + cnt[j][1] * 1LL * f % DVS * j) % DVS;
    }
    for (int j(2); j <= i; ++j) {
      for (int k(1); j - 1 <= i - k; ++k) {
        cnt[i][j] = (cnt[i][j] + cnt[i - k][j - 1] * 1LL * cnt[k][1]) % DVS;
      }
    }
  }
  if (type) {
    for (int i(0); i != Pt - N; ++i) {
      int t(cnt[N][K - i]);
      for (int j(1); j <= Pt - 1 - N - i; ++j) t = t * 1LL * j % DVS;
      ans = (ans + t) % DVS;
    }
  } else {
    for (int i(K); i <= N; ++i) ans = (ans + cnt[N][i]) % DVS;
  }
  cout << ans << endl;
  return 0;
}