题解：AT_agc064_d [AGC064D] Red and Blue Chips

· · 题解

感觉不难。

首先我们可以建出树，然后最终序列就是后序遍历。（这里儿子遍历顺序从大到小）。

由于父亲又大于儿子，所以后序遍历可以唯一确定树，只需满足末尾是 n 即可。

你发现，在后续遍历中，如果 i=1 或 a_i<a_{i-1}，则一定为叶子，否则一定不为叶子，于是一个字符串 S 合法当且仅当存在排列 p 使得 p_n=n 且 \forall S_i=R,a_i<a_{i-1},i>1。

考虑怎么 check，将序列划分为 R 的连续段后面跟上一个 B，贪心地为长的连续段分配大的 B 即可。

也就是说，考虑所有 B 前面的 R 数量 pre_1,\dots,pre_k（pre_1\le \dots \le pre_k），所有 B 的连续段长为 l_1,\dots,l_k（l_1\dots \le l_k），则有

\sum_{j=1}^{i}l_j\le pre_i

直接 dp 即可，注意处理多重集排列和第一段。

复杂度调和级数 \mathcal{O}(n^3\log n)，

#include <bits/stdc++.h>
/*
#include<atcoder/all>
using namespace atcoder;
*/
using namespace std;
namespace __LYC__
{
    template<typename T>
    T exgcd(T a, T b, T &x, T &y){
        if (b == 0) return x=1,y=0,a;
        T g = exgcd(b, a % b, x, y);
        T tmpx = x;x = y;y = tmpx - y * (a / b);
        return g;
    }
    template<typename T>
    T finv(T a, T m){
        T x, y;
        if (exgcd(a, m, x, y) != 1) return 0;
        x %= m;
        if (x < 0) x += m;
        return x;
    }
};
#define lowbit(x) ((x)&(1+(~(x))))
using __LYC__::finv, __LYC__::exgcd;
// #define int long long
using ll=long long;
using uint=unsigned int;
using ushort=unsigned short;
using ull=unsigned long long;
using LLL=__int128;
using uLLL=unsigned __int128;
const int N=300, INF = 1e9,P=998244353;
int n,m;
void print(vector<int> &A){
    cout<<A.size()<<"\n";for(int i=0;i<A.size();++i) cout<<A[i]<<" \n"[i==A.size()-1];}
#define debug(x) cout<<#x<<": "<<x<<"\n";
string str;
vector<int> CCF;
int dp[N+5][N+5];
int inv[N+5],fac[N+5];
void solve(int idT){
    cin>>n>>str;
    int num=0;
    for(int i=1;i<n;++i){
        if(str[i-1]=='B'){
            CCF.emplace_back(num);
        }
        else ++num;
    }
    for(int i=0;i<=CCF.size();++i) dp[i][0]=inv[i];
    for(int i=1;i<=num;++i){
        for(int j=CCF.size()-1;j>=0;--j){
            for(int k=0;k<=num-i;++k){
                for(int l=1;j+l<=CCF.size()&&k+l*i<=CCF[j+l-1];++l){
                    dp[j+l][k+l*i]=(dp[j+l][k+l*i]+(ll)dp[j][k]*inv[l])%P;
                }
            }
        }
    }
    int res=0;
    for(int i=0;i<=num;++i){
        res+=dp[CCF.size()][num-i];
        if(res>=P) res-=P;
    }
    cout<<(ll)res*fac[CCF.size()]%P<<"\n";
}
signed main(){
    inv[0]=inv[1]=1;
    fac[0]=fac[1]=1;
    for(int i=2;i<=N;++i){
        inv[i]=(ll)(P-P/i)*inv[P%i]%P;
        fac[i]=(ll)fac[i-1]*i%P;
    }
    for(int i=3;i<=N;++i) inv[i]=(ll)inv[i]*inv[i-1]%P;
    ios::sync_with_stdio(0),cin.tie(0);
    int Tcases = 1;
    //cin >> Tcases;
    for(int i=1;i<=Tcases;i++) solve(i);
    return 0;
}
/*
RBRB
BRRB
RRBB

1 2
0 2 2
1 1 1
*/