题解：CF1439D INOI Final Contests

Z1qqurat · 2025-06-06 18:07:17 · 题解

锣鼓题解一篇也没看懂，我太🥬了！不过有一说一，所有的题解都感觉是知道了最终结果然后反过来写的“代码解说”一类的东西，没有思路比较顺畅的😨。

• 其实这种贡献和看到之后的第一反应应该是转期望，然后就可以只用维护一个 dp 值了。但是实际上没办法转期望来做，这将在之后被说明。

• 我们先考虑一个 dp 对象：记 g(i,j) 表示一共有 i 个位置，j 个人的时候，这 j 个人都找到了位置坐的情况下，所有的 (a\{j\},b\{j\}) 的权值之和。

  转移考虑枚举第 i 个人坐的位置 j，不妨设 b_i=\mathtt{'L'}，那么 a_i 可以取 1\sim j，问题来了，我们没办法确定 1\sim j 是否有人坐了，所以我们不能知道是否每一个 1\sim j 中的数都可以作为 a_i。而这个信息也不能塞到状态里面，于是这个转移思路就倒闭了。

• 这个做法倒闭的原因是你没法确定 1\sim j 的被占用情况。这时候有一种特殊情形：如果 i=j，那么假如最终 i 坐到了 j，那么 1\sim j-1 一定都是已经被占用了的，所以 a_i 可以取 1\sim j-1 中任意的一个数。那么我们只需要把前 i-1 个数分到 j-1,n-j 两块里面。

  假如我们得出了 i=j 的结果，那么可以把 i>j 的情形按照位置占用情况分成若干个极长被占用位置连续段，然后就可以转化为 i=j 的若干段拼起来的结果了。

• 容易发现这个贡献的计算需要知道方案数，所以我们先求一个 f_1(i) 表示有 i 个位置，i 个人，然后使得每个人都找到了位置坐的 (a,b) 对数。转移枚举第 i 个人所在位置 j：

  • 先考虑第 i 个人的贡献：如果 b_i=\mathtt{'L'}，那么 a_i\in[1,j] 都可以；如果 b_i=\mathtt{'R'}，那么 a_i\in[j,i] 都可以。所以 (a_i,b_i) 共 i+1 种。
  • 然后我们考虑前 i-1 个人的贡献，实际上就是把它们分到两块里面，这里分组的方案数是 \binom{i-1}{j-1}，然后这两段的贡献分别是 f_1(j-1),f_1(i-j)。

  即 f_1(i)=(i+1)\sum\limits_{j=1}^i \binom{i-1}{j-1}f_1(j-1)f_1(i-j)。

• 然后记 f_2(i) 表示有 i 个位置，i 个人，每个人都找到了位置，此时所有方案的 \sum\limits_{j=1}^i |a_j-p_j| 之和。转移思路就跟上面的方案数类似了，只是在算贡献的时候原本对于方案数，贡献是 1，而对于权值和，贡献就是权值了（我在说什么废话？）。

  • 第 i 个人的贡献：(i+1)\sum\limits_{j=1}^i\binom{i-1}{j-1}(f_1(j-1)f_2(i-j)+f_2(j-1)f_1(i-j))。
  • 前 i-1 个人的贡献：\sum\limits_{j=1}^i \binom{i-1}{j-1}(\frac{j(j-1)}{2}+\frac{(i-j+1)(i-j)}{2})f_1(j-1)f_1(i-j)。

  你发现这里面贡献计算方式是乘积，所以你转期望就相当于转了个寂寞。而且这题转了期望之后并不能将答案写成若干个概率之和的形式，所以倒闭了。

• 接下来我们来合并求出 i>j 的情况，记 g_1(i,j) 表示有 i 个位置，j 个人，然后使得每个人都找到了位置坐的 (a,b) 对数。

  考虑一点简单递推，设 l 为 1\sim i 中最长的全部被占用了的前缀长度，枚举 l\in[0,j]。

  • 如果 l=0，就是 g_1(i-1,j)。

  • 否则 l>0，考虑扔掉 l 这一段，那么 l+1 位置肯定得是 0，所以就剩下一段长为 i-l-1 的子结构。

  所以贡献为 \binom{j}{l}f_1(l)g_1(i-l-1,j-l)。

• 记 g_2(i,j) 表示有 i 个位置，j 个人，然后使得每个人都找到了位置坐的贡献总和。

  设 l 为 1\sim i 中最长的全部被占用了的前缀长度，枚举 l\in[0,j]。

  • 如果 l=0，就是 g_2(i-1,j)。

  • 否则 l>0，贡献为 \binom{j}{l}(f_1(l)g_2(i-l-1,i-l)+f_2(l)g_1(i-l-1,i-l))。

• 最终答案就是 g_2(n,m)，初始值就是 f_1(0)=1,g_1(0,0)=1，其他的项都是 0。需要预处理组合数。

给出参考代码。

#include <bits/stdc++.h>
using namespace std;
using tp = int;
constexpr tp INF = 1e9;
#define FULL(a) begin(a), end(a)
#define ALL(a, l, r) begin(a) + l, begin(a) + r + 1

template <typename T>
bool ckmax(T &x, T y) {
   if (y > x) return x = y, 1;
   return 0;
}
template <typename T>
bool ckmin(T &x, T y) {
   if (y < x) return x = y, 1;
   return 0;
}

tp mod;
tp norm(tp x) { return x + (x < 0) * mod - (x >= mod) * mod; }
void add(tp &x, tp y) { x = norm(x + y); }
tp pow(tp x, tp y) {
   tp z = 1;
   for (; y; x = 1ll * x * x % mod, y >>= 1)
      if (y & 1) z = 1ll * z * x % mod;
   return z;
}

void QWQ() {
   ios::sync_with_stdio(false), cin.tie(nullptr);
}

constexpr tp N = 505;
tp n, m;
array<tp, N> fac, ifc, f1, f2;
array<array<tp, N>, N> c, g1, g2;

tp bnm(tp n, tp m) {
   if (n < 0 || m < 0 || n < m) return 0;
   return 1ll * fac[n] * ifc[m] % mod * ifc[n - m] % mod;
}

tp HARUTO() {
   cin >> n >> m >> mod;
   for (tp i = 0; i <= n; ++i) {
      c[i][0] = 1;
      for (tp j = 1; j <= i; ++j) c[i][j] = norm(c[i - 1][j - 1] + c[i - 1][j]);
   }

   f1[0] = 1;
   for (tp i = 1; i <= n; ++i) {
      for (tp j = 1; j <= i; ++j) {
         add(f1[i], 1ll * f1[j - 1] * f1[i - j] % mod * c[i - 1][j - 1] % mod);
         tp w = 1ll * f1[j - 1] * f2[i - j] % mod + 1ll * f2[j - 1] * f1[i - j] % mod;
         add(f2[i], 1ll * (i + 1) * norm(w) % mod * c[i - 1][j - 1] % mod);
         add(f2[i], 1ll * norm(c[j][2] + c[i - j + 1][2]) * f1[j - 1] % mod * f1[i - j] % mod * c[i - 1][j - 1] % mod);
      }
      f1[i] = 1ll * (i + 1) * f1[i] % mod;
   }

   g1[0][0] = 1;
   for (tp i = 1; i <= n; ++i) {
      for (tp j = 0; j < i; ++j) {
         g1[i][j] = g1[i - 1][j], g2[i][j] = g2[i - 1][j];
         for (tp l = 1; l <= j; ++l) {
            add(g1[i][j], 1ll * f1[l] * g1[i - l - 1][j - l] % mod * c[j][l] % mod);
            add(g2[i][j], 1ll * f1[l] * g2[i - l - 1][j - l] % mod * c[j][l] % mod);
            add(g2[i][j], 1ll * f2[l] * g1[i - l - 1][j - l] % mod * c[j][l] % mod);
         }
      }
      g1[i][i] = f1[i], g2[i][i] = f2[i];
   }
   cout << g2[n][m] << "\n";
   return 0;
}

int main() {
   QWQ();
   tp t = 1;
   while (t--) HARUTO();
   return 0;
}