题解：AT_agc077_d [AGC077D] Range Replace 2

dyc2022 · 2026-06-03 20:57:10 · 题解

更好的阅读体验

非常具有教育意义的一个数数题！

将区间 [l, r] 赋值为 \frac{r(r-1)}{2} + l 这个操作，实际就是将每个区间 [l, r] 映射成一个数字，且所有区间所代表的数字互不相同。

那么我们需要解决这样个问题：有一个二元组序列 a，初始都是 (0, 0)。你可以进行任意次“选择一个区间 [l, r]，将 a_l \sim a_r 全部赋值为二元组 (l, r)”操作，求可以产生多少种本质不同的序列 a。

首先我们先考虑对操作结束之后，不包含 (0, 0) 的序列 a 计数；假设 f_i 表示有多少种长度为 i 且本质不同的，不包含 (0, 0) 的序列。很显然如果允许存在 (0, 0)，只需要将若干个 f_i 组合起来即可。接下来仅考虑 f 怎么求，且下文讨论的所有 a 的默认不含有 (0, 0)。

那么我们试图刻画怎样的 a 是合法的。我们声称，一个合法的 a 可以通过有限次如下操作变成全 (0, 0)。

选择一个区间 [l, r]，使 a_l \sim a_r 的取值均为 (l, r) 或 (0, 0) 之一，并将 a_l \sim a_r 全部置为 (0, 0)。

我们称之为一次消除操作。对应地，我们将题目所给的操作称为一次推平操作。

正确性是显然的。对于一个满足上述条件的序列，我们将进行消除操作倒过来，则可以得到从全 (0, 0) 经过一系列推平操作得到这个序列的一种方案；对于一个可以通过推平操作得到的序列 a，也可以将操作序列反转，得到进行消除操作使序列变成全 (0, 0) 的方案。

那么假设现在已经得到了一个合法的序列 a，自然也将会客观存在一些消除操作序列；操作序列中的操作之间也存在一些先后顺序的限制，比如对于 \{(1, 2), (2, 3), (2, 3)\} 这个序列，[1, 2] 操作必须在 [2, 3] 这次操作之前进行。假设我们将所有这种先后关系的操作连有向边（后消除的向先消除的连边），则我们一定会得到一个 DAG，而 DAG 的任意一个拓扑序都是满足条件的。

随后我们注意到了一件事情：当 DAG 的形态不同，最终的序列 a 必然不同。

形成新的 DAG 后，一定存在至少两个区间，他们之间的先后关系发生了反转。

考虑两个区间 [l_1, r_1] 必须在 [l_2, r_2] 前进行，那么就意味着 a 序列上 [l_1, r_1] 区间上至少存在一个 (l_2, r_2)，且 a 序列上 [l_2, r_2] 上不存在 (l_1, r_1)。

则假设我们将这对先后关系反转，即 [l_1, r_1] 必须在 [l_2, r_2] 后进行，那么限制就变成 a 序列上 [l_1, r_1] 区间上不存在任何 (l_2, r_2)，且 a 序列上 [l_2, r_2] 上至少有一个 (l_1, r_1)。

容易发现这两个限制描绘出的序列 a 是不一样的。

因此我们考虑对合法的 DAG 计数，考虑主旋律，进行 DAG 容斥！

具体是如何操作的呢？我们考虑找到 DAG 上入度为 0 的集合恰好是 S，即可以作为最后一次消除操作的操作集合。那么由 f 的定义，有

f_i = \sum_S \left(S \space \text{对应了多少种序列} \space a\right)

“恰好”是不好处理的。考虑转化为钦定，假设 T 是钦定入度为 0 的集合，并进行容斥，可以得到

f_i = \sum_T (-1)^{|T| - 1}\left(T \space \text{对应了多少种序列} \space a\right)

我们假设 g_i 表示，长度为 i 且不包含 (0, 0) 的序列，固定 i 是在可能在最后一次操作中消除的，则对于它所对应地所有 T，(-1)^{|T|-1} 之和。

我们考虑 T 的转移：

如果最后一次被修改为 (0, 0) 的位置只有 i，则前 i-1 个位置对 i 不会产生任何影响；在最后一次操作之前，整个序列应该是形如 \{(0, 0), (0, 0), \cdots, (0, 0), (l, i)\}。那么前 i-1 个位置有 f_{i-1} 种方案，l 有 i 中选择。因此在此情况下，g_i \leftarrow f_{i-1} \cdot i。
否则我们枚举上一个，在可能在最后一次操作中被修改成 (0, 0) 的位置 j。那么在这种情况下，由于 a_j 在最后一次操作之前都不是 (0, 0)，因此我们将序列分割成了相互独立的两段。
- 若 a_j = a_i，那么 [j+1, i-1] 区间内可以任意消除，方案数为 f_{j-i-1}；由于此时 j 是一个规模更小的子问题的末尾位置，所以 [1, j] 这个区间的方案数是 g_j。\ 因此 g_i \leftarrow g_j \cdot f_{i-j-1}。
- 若 a_j \not = a_i，那么 [j+1, i-1] 区间内可以任意消除，方案数为 f_{j-i-1}；由于此时 j 是一个规模更小的子问题的末尾位置，所以 [1, j] 这个区间的方案数是 g_j。但是由于 a_i 和 a_j 不同，因此它们要在两次不同的操作中被依次置为 (0, 0)，所以我们需要给包含 j 的操作确定一个右端点，可以取遍 [j, i) 中的每一个值，方案数为 i-j；我们还要给包含 i 的操作确定一个左端点，可以取遍 (j, i] 中的每一个值，方案数为 i-j；由于我们多了一次操作，所以给 T 的大小增加了 1，因此还要乘上 -1 的系数。\ 因此 g_i \leftarrow -g_j \cdot f_{i-j-1} \cdot (i-j)^2。

最后考虑 g \to f 的转移。这是类似的。我们枚举可能在最后一次操作中被消除的最后一个位置 j，那么同理，j 将 [1, i] 分割成了相互独立的两个部分。[i+1, j] 可以任意消除，方案数为 f_{i-j}；由于我们确定了 j 可能在最后一次操作中被消除，因此前 j 个位置的方案数是 g_j；我们还要给包含 j 的操作钦定一个右端点，可以取遍 [j, i] 中的每一个值，方案数为 i-j+1。\ 因此 f_i \leftarrow f_{i-j} \cdot g_{j} \cdot (i-j+1)。

那么这道题就做完了，复杂度 O(n^2)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 5006
using namespace std;
int n,MOD,f[N],g[N],h[N];
inline void add(int &x,int y) {x+=y,x-=x>=MOD?MOD:0;}
inline void dec(int &x,int y) {x+=MOD-y,x-=x>=MOD?MOD:0;}
main()
{
  scanf("%d%d",&n,&MOD),f[0]=h[0]=1;
  for(int i=1;i<=n;i++)
  {
    g[i]=1ll*i*f[i-1]%MOD;
    for(int j=0;j<i;j++)
    {
      add(g[i],1ll*g[j]*f[i-j-1]%MOD);
      dec(g[i],1ll*g[j]*f[i-j-1]%MOD*(i-j)%MOD*(i-j)%MOD);
    }
    for(int j=1;j<=i;j++)
      add(f[i],1ll*f[i-j]*(i-j+1)%MOD*g[j]%MOD);
  }
  for(int i=1;i<=n;i++)
  {
    add(h[i],f[i]),add(h[i],h[i-1]);
    for(int j=1;j<i;j++)add(h[i],1ll*h[i-j-1]*f[j]%MOD);
  }
  printf("%d\n",h[n]);
  return 0;
}