[CCPC2024 重庆站] Pico Park 题解

FFTotoro · 2025-08-09 12:55:08 · 题解

下文中的所有下标从 1 开始；代码中下标均从 0 开始。请读者注意这一点。

针对排列的计数 DP 有的时候很难找到突破口，并且这个左右射击的形式看起来十分混乱，尝试先观察性质。

考虑建图找性质，假设一个玩家 x 通过射击将另一个玩家 y 缩小了，那么连边 x\to y。可以得出每个点的出度最多为 1，并且不可能出现环——于是这个图由若干条有向链 u_1\to u_2\to\cdots\to u_k 构成，链头就是没有被缩小的玩家。故最终存活的玩家数量即为极长链的数量——接下来开始尝试挖掘性质。

• 性质 \textbf{1}：一条链上的所有玩家编号必然位于一段区间内，并填满了这个区间（即将链上的玩家按照初始时在数轴上的位置重新排序，那么他们是连续的一段）。于是可以据此进行 DP，设 f_{i,j} 表示考虑了前 i 个玩家，已经形成了 j 条极长链（存活了 j 个人）的方案数。转移时考虑加入一段区间 [l,r]（即进行转移 f_r\gets f_{l-1}\cdot w，w 为转移系数，在后面将会解释其计算方法），表示初始位置在 [l,r] 间的玩家以某种顺序形成了一条极长链；
• 性质 \textbf{2}：并不是所有区间 [l,r] 都存在一种射击顺序，使得最后可以形成一条极长链——一个区间合法（存在一种射击顺序），当且仅当按玩家初始顺序排列（即依次考虑玩家 l,l+1,\ldots,r-1,r），他们的射击方向分别为 \texttt{RR}\ldots\texttt{RRLL}\ldots\texttt{LL}，即一段 \texttt{R}（可以为空）拼接上一段 \texttt{L}（可以为空）。这个结论是显然的——只需要考虑如果存在 \texttt{LR} 那么一定会有 \ge 2 人存活，不可能形成一条链。

现在问题转换为给合法区间 [l,r] 内的玩家安排一个射击顺序，使得这个区间能形成一条极长链。注意，这个值不是最终直接进行转移的系数，因为还要安排这个区间的玩家在所有玩家中的射击时间点——即，假设考虑完之前的转移后，总共还有 m 人没有确定顺序，方案数还要乘上一个 C_{m}^{r-l+1} 才能加入转移（即从剩下的位置中选择 r-l+1 个给当前考虑的玩家）。

设连续段 [l,r] 内有 y 个 \texttt{R} 和 x 个 \texttt{L}，接下来开始分类讨论：

• - 该连续段是最靠左的连续段（$l=1$）：最靠左的玩家随时都可以射击（因为其子弹影响不到任何玩家），右边的 $x-1$ 个玩家需要按顺序射击才能保证形成一条链。方案数为 $x$，即选择最靠左玩家何时射击； - 该连续段不是最靠左的连续段（$l>1$）：最靠左的玩家必须在第二靠左的玩家将其缩小后再射击（相当于把最靠左玩家的射击“跳过”，使其不会“误伤”更靠左的其他连续段的玩家），其余与上面一致。方案数为 $x-1$，同样是选择最靠左玩家何时射击，只是此时不能选择第一个射击了。
• - $a$ 先射击：此时所有的 $\texttt{L}$ 需要依次射击，除了 $b$ 以外的其他 $\texttt{R}$ 也需要依次射击，只有一开始就被缩小的 $b$ 可以在 $a$ 射击后的任意时刻射击（因为它不管何时射击都会被跳过）——计数就考虑先从 $x+y-1$ 个位置中选 $x$ 个位置分配给 $\texttt{L}$，接着选择 $b$ 何时射击有 $y-1$ 种方案，总的方案数为 $C_{x+y-1}^x(y-1)$； - $b$ 先射击：此时所有的 $\texttt{R}$ 需要依次射击，除了 $c$ 以外的其他 $\texttt{L}$ 也需要依次射击，但是这个时候 $c$ 只需要在 $b$ 之后射击即可，所以有 $x$ 种方案，总的方案数为 $C_{x+y-1}^xx$； - $c$ 先射击：与 $b$ 同理，方案数为 $C_{x+y-1}^yy$； - $d$ 先射击：与 $a$ 同理，方案数为 $C_{x+y-1}^y(x-1)$。

据此直接进行 DP，时间复杂度 O(n^3)。更多细节可以参考代码。

放代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000,P=998244353;
static int f[N+1],fi[N+1];
inline int add(int x,int y){
  int s=x+y; if(s>=P)s-=P; return s;
}
inline void self_add(int &x,int y){
  if((x+=y)>=P)x-=P;
}
inline int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=1ll*r*a%P;
    a=1ll*a*a%P,b>>=1;
  }
  return r;
} // 快速幂，用于求逆元
inline int com(int n,int m){
  return 1ll*f[n]*fi[m]%P*fi[n-m]%P;
} // 组合数
inline int coef(int l,int r,int n,bool L,bool R){
  if(!r){
    if(L)return 1ll*com(n,l)*l%P;
    return 1ll*com(n,l)*(l-1)%P;
  }
  if(!l){
    if(R)return 1ll*com(n,r)*r%P;
    return 1ll*com(n,r)*(r-1)%P;
  }
  int x=add(1ll*com(l+r-1,r)*r%P,1ll*com(l+r-1,l)*l%P),
    y=add(1ll*com(l+r-1,r)*(l-1)%P,1ll*com(l+r-1,l)*(r-1)%P);
  return 1ll*com(n,l+r)*add(x,y)%P;
} // 按照文中所述方式计算转移系数
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  for(int i=f[0]=1;i<=N;i++)
    f[i]=1ll*f[i-1]*i%P;
  fi[N]=qpow(f[N],P-2)%P;
  for(int i=N;i;i--)
    fi[i-1]=1ll*fi[i]*i%P;
  int n; string s; cin>>n>>s;
  auto cnt=[&](int l,int r){
    int cr=0,cl=0;
    for(int i=l;i<=r&&s[i]=='R';i++)cr++;
    for(int i=r;i>=l&&s[i]=='L';i--)cl++;
    return make_pair(cr,cl);
  }; // 计算左侧 R 数量和右侧 L 数量
  vector f(n,vector<int>(n+1));
  for(int i=0;i<n;i++)
    for(int j=i;~j;j--){
      auto [r,l]=cnt(j,i);
      if(l+r!=i-j+1)break; // 判断是否合法
      for(int k=0;k<=j;k++)
        if(int w=j?f[j-1][k]:!k;w)
          self_add(f[i][k+1],1ll*w*coef(l,r,n-j,!j,i==n-1)%P);
    } // 状态转移过程
  for(int i=1;i<=n;i++)
    cout<<f[n-1][i]<<' ';
  cout<<endl;
  return 0;
}