[AGC064D] Red and Blue Chips 题解

题目链接

点击打开链接

题目解法

挺牛的题

这种计数本质不同的结果的题，一个很不错的切入口是判断结果的合法性

令 B 的总数为 \(m\)
我们把结果串先挂在第 \(m\) 个 B 上
考虑从后往前枚举原串（最后一个 B 不枚举），相当于我们在倒序模拟操作过程

1. 枚举到 B，我们相当于要把后面的一个 B 的序列劈成两半，前一半挂在当前这个 B 上
2. 枚举到 R，把后面任意一个 B 的序列的开头去掉一个 R

举个例子：
原串为 RBBRRB，结果串为 RRBRBB
一开始第 \(3\) 个 B 上有序列 RRBRBB
枚举到第 \(5\) 个字符 R 时，去掉第 \(3\) 个 B 开头的 R
枚举到第 \(4\) 个字符 R 时，去掉第 \(3\) 个 B 开头的 R
枚举到第 \(3\) 个字符 B 时，当前第 \(3\) 个 B 的串为 BRBB，分成 BRB（第 \(2\) 个 B 对应的串） 和 B（第 \(3\) 个 B 对应的串）
枚举到第 \(2\) 个字符 B 时，把第 \(2\) 个 B 的串分成 B 和 RB
最后直接去掉第 \(2\) 个 B 开头的 R 即可

抽象一下这个问题：
我们把结果串 B 前的最长连续 A 的个数序列称为 \(a\)（顺序）
原串 B 前的最长连续 A 的个数序列称为 \(b\)（逆序）
那么结果串合法的充要条件是：

1. \(\sum a_i=n-m\)
2. 因为 \(a_1\) 是不能动的，所以把 \(a_2,...,a_n\) 从大到小排序之后，需要满足 \(\sum a_i\ge \sum b_i\)

这个问题是好计数的，具体见代码，时间复杂度是 \(O(n^2\log^2 n)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=310,P=998244353;
int n,pr[N],f[N][N],g[N][N];
char str[N];
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
int fac[N],ifac[N];
int qmi(int x,int y){
    int res=1;for(;y;y>>=1){ if(y&1) res=1ll*res*x%P;x=1ll*x*x%P;}
    return res;
}
void comb(int n){
    fac[0]=1;F(i,1,n) fac[i]=1ll*fac[i-1]*i%P;
    ifac[n]=qmi(fac[n],P-2);DF(i,n-1,0) ifac[i]=1ll*ifac[i+1]*(i+1)%P;
}
int main(){
    read(n);
    comb(n);
    scanf("%s",str+1);
    int cnt=0,m=0;
    F(i,1,n){
        if(str[i]=='R') cnt++;
        else pr[++m]=cnt,cnt=0;
    }
    reverse(pr+1,pr+m+1);
    F(i,1,m) pr[i]+=pr[i-1];
    int R=n-m;
    F(i,pr[1],R) f[i][1]=1;
    DF(i,R,1){
        F(j,0,R) F(k,1,R/i+1) if(f[j][k]){
            int mxq=min((R-j)/i,m-k);
            F(q,0,mxq){
                if(j+q*i<pr[k+q]) break; 
                inc(g[j+q*i][k+q],1ll*f[j][k]*ifac[q]%P);
            }
        }
        F(j,0,R) F(k,1,R/i+1) f[j][k]=g[j][k],g[j][k]=0;
    }
    int ans=0;
    F(i,1,m) inc(ans,1ll*f[R][i]*ifac[m-i]%P);
    ans=1ll*ans*fac[m-1]%P;
    printf("%d\n",ans);
    return 0;
}