题解：AT_awtf2025_b Movies

dyc2022 · 2026-06-22 20:12:06 · 题解

更好的阅读体验

什么题哦。

称一个日期被安排电影，为这个日期被“选择”。

首先考虑对于单个 S 如何求 f(S)。那么有一个较为显然的贪心：

• 按照右端点从小到大的顺序枚举区间。如果该区间内部还有未被选择的位置，那么就找到最靠左的未被选择的位置，将这个位置选择；否则无事发生。

那么我们应用这个策略，会发现对于每个 S，都客观存在一个长度为 n 的 01 序列 t，其中 t_i = 1 表示在最终状态下第 i 个位置被选择；t_i = 0 表示第 i 个位置不被选择。

那么按照一般的做法，我们会想要把贡献拆到每个 t_i 上，比如去对每个 i 分别计数有多少中方案使 t_i = 1 等等。但是在这题中我们似乎难以这么做，因为 i 这个位置选不选，与前面位置的状态是有很大关系的。

虽然单个位置和位置之间是不独立的，但我们发现，如果我们观察这个序列 t 的极长全为 1 的连续段（下称为“极长连续段”），会发现段与段之间是独立的。原因是，假设有两个不交的极长连续段 [l_1, r_1] 和 [l_2, r_2]，那么会选择 [l_1, r_1] 中的位置的区间 i 必须满足 L_i \isin [l_1, r_1]，会选择 [l_2, r_2] 中的位置的区间 j 必须满足 L_j \isin [l_2, r_2]。容易发现在此条件下，所有的 \boldsymbol i 和所有的 \boldsymbol j 构成的集合是不交的。这意味着，“同时存在 [l_1, r_1] 和 [l_2, r_2] 这两个极长连续段”的方案数，可以直接表示成“存在 [l_1, r_1] 极长连续段”的方案数，和“存在 [l_2, r_2] 极长连续段”的方案数的乘积。这启发我们，可以把贡献拆到每个极长连续段上。

我们这样设计 dp 状态：f_{i, l, r} 表示仅考虑排序后的前 i 个区间中左端点在 [l, r] 内的区间，有多少种方案，使选择完区间后，t 上的 [l, r] 区间恰好是一个极长连续段。

接下来考虑 f 的转移。

• - $S$ 中仅选择了第 $i$ 个区间，那么将会选择第 $L_i$ 个位置：$f_{i, L_i, L_i} \leftarrow 1$。 - 若 $[L_i, R_i] \subseteq [l, r]$，则说明这个区间中无法选择任何点，因此无事发生：$f_{i, l, r} \leftarrow f_{i-1, l, r}$。 - 若 $L_i \isin [l, r] \land R_i \ge r$：第 $i$ 个区间选择了 $r$ 这个位置：$f_{i, l, r} \leftarrow f_{i-1, l, r-1}$。 - 若第 $i$ 个区间选择了 $L_i$，且 $L_i$ 成为了新的极长连续段的左端点：$f_{i, L_i, r} \leftarrow f_{i, L_i + 1, r}$。 - 若 $L_i \isin [l, r]$，且第 $i$ 个区间选择的点不是 $l$ 或 $r$。那么我们枚举选择的点 $x$，那么选择 $x$ 后将会合并两个极长连续段。因此有：$f_{i, l, r} \leftarrow f_{i, l, x-1} \cdot f_{i, x+1, r}$。

接下来考虑如何求出答案。假设 g_{i, j} 表示，仅考虑 t 的前 i 个位置，有 j 个 1 的方案数。那么有转移：

最后的答案就是 \sum \limits_{i = 1}^n i \cdot g_{n, i}。

假设 m = O(n^2)，那么 f 的转移是 O(n^5)（瓶颈在于枚举 x），g 的转移是 O(n^3)。但是 f 的转移常数极小，因此可以通过。

至此，问题在 O(n^5) 的时间内得到解决。

#include<bits/stdc++.h>
#define endl '\n'
#define N 106
#define MOD 998244353
using namespace std;
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;}
int n,m,f[N][N],tf[N][N],g[N][N];
struct Node {int l,r;} a[N*N];
main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)scanf("%d%d",&a[i].l,&a[i].r);
  sort(a+1,a+1+m,[](Node x,Node y) {
    return x.r<y.r;
  });
  for(int i=1;i<=m;i++)
  {
    for(int l=1;l<=n;l++)
      for(int r=l;r<=n;r++)tf[l][r]=f[l][r];
    add(f[a[i].l][a[i].l],1);
    for(int l=1;l<=n;l++)
      for(int r=l;r<=n;r++)
      {
        if(l<=a[i].l&&a[i].r<=r)add(f[l][r],tf[l][r]);
        if(l<=a[i].l&&a[i].l<=r)
        {
          if(r<=a[i].r)add(f[l][r],tf[l][r-1]);
          for(int j=max(l+1,a[i].l);j<=min(r-1,a[i].r);j++)
            add(f[l][r],1ll*tf[l][j-1]*tf[j+1][r]%MOD);
        }
      }
    for(int r=a[i].l+1;r<=n;r++)
      add(f[a[i].l][r],tf[a[i].l+1][r]);
  }
  int ans=0;
  f[0][0]=1;
  for(int i=1;i<=n;i++)
    for(int j=0;j<=i;j++)
    {
      add(g[i][j],g[i-1][j]);
      add(g[i][j],f[i-j+1][i]);
      for(int k=0;k<j;k++)
        add(g[i][j],1ll*f[i-k+1][i]*g[i-k-1][j-k]%MOD);
    }
  for(int i=0;i<=n;i++)
    add(ans,1ll*i*g[n][i]%MOD);
  printf("%d\n",ans);
  return 0;
}