题解：AT_abc238_h [ABC238Ex] Removing People

· · 题解

Solution

这种简单题为什么评分这么高。

概率期望看起来很没有意义，所以变为对全部的 n! 种删人方式，求得到的代价之和。

发现“删人”这个事情不好记录状态，但是“加人”就很方便。我们可以设 dp_{l,r} 表示，环上有相邻的两人 l 和 r，且 r 在 l 的顺时针方向。我们要把 l 和 r 之间的所有人加进去，有多少种方案，以及这些方案的代价之和。

假设我们把 k 加了进去（l<k<r）。考虑枚举是谁把 k 顶掉的，发现只能是 l 或 r（前提是 l 的方向为 R，或者 r 的方向是 L，对这两种分别求和）。然后转化到 dp_{l,k} 和 dp_{k,r}。

对于这两种状态，你需要用 \binom{r-l-2}{k-l-1} 种方案将两边归并起来（合并两个区间的时候要处理方案、代价之和的变化，可以参考我的代码。）

复杂度 O(n^3)，轻松通过本题。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=600+10,MOD=998244353;
struct DP {int ans,cnt;}dp[MAXN][MAXN];
DP operator +(DP A,DP B) {return {(A.ans+B.ans)%MOD,(A.cnt+B.cnt)%MOD};}
DP operator *(DP A,DP B) {return {(A.ans*B.cnt+B.ans*A.cnt)%MOD,A.cnt*B.cnt%MOD};}
DP operator ^(DP A,int B) {return {A.ans*B%MOD,A.cnt*B%MOD};}
int n,op[MAXN],C[MAXN][MAXN];
int qpow(int base,int p) {
    int ans=1;
    while(p) {
        if(p&1) ans=ans*base%MOD;
        base=base*base%MOD,p>>=1;
    }
    return ans;
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    ffor(i,0,n) {
        C[i][0]=1;
        ffor(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
    }
    string S;
    cin>>S;
    ffor(i,1,n) if(S[i-1]=='R') op[i]=op[i+n]=1;
    ffor(i,1,n+n) dp[i][i+1]={0,1};
    ffor(len,3,n+1) for(int l=1,r=len;r<=n+n;l++,r++) {
        ffor(k,l+1,r-1) {
            DP tmp=(dp[l][k]*dp[k][r])^C[k-l-1+r-k-1][k-l-1];
            DP ad={0,0};
            if(op[l]) ad=ad+tmp,ad.ans=(ad.ans+tmp.cnt*(k-l))%MOD;
            if(!op[r]) ad=ad+tmp,ad.ans=(ad.ans+tmp.cnt*(r-k))%MOD;
            dp[l][r]=dp[l][r]+ad;
        }
    }
    int ans=0;
    ffor(i,1,n) ans=(ans+dp[i][i+n].ans)%MOD;
    ffor(i,1,n) ans=ans*qpow(i,MOD-2)%MOD;
    cout<<(ans%MOD+MOD)%MOD;
    return 0;
}