题解：CF1439D INOI Final Contests

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

其实这种贡献和看到之后的第一反应应该是转期望，然后就可以只用维护一个 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$ 。需要预处理组合数。
$f_1,f_2$ 的计算是 $O\left(n^2\right)$ 的， $g_1,g_2$ 的计算是 $O\left(n^3\right)$ 的。出题人说有 $n^2$ 做法，我不会，代码看不懂。感觉是推式子神秘做法，我太🥬了。

给出参考代码。

CPP

#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;
}

题解：CF1439D INOI Final Contests

文章操作

相关推荐

评论

题解：CF1439D INOI Final Contests