【学习笔记】[AGC064D] Red and Blue Chips

学习笔记】[AGC064D] Red and Blue Chips"/>

【学习笔记】[AGC064D] Red and Blue Chips

神一样的 Kidulthood 考场上就看出来了这道题其实不难，但是祂没时间写了😅

假设最后从底部到顶部的位置序列为 { x i } \{x_i\} {xi​}，那么每一步的操作就是固定的

将结论拓展可以得到，如果 x i > x i + 1 x_i>x_{i+1} xi​>xi+1​，那么 x i x_{i} xi​必须是蓝色

转化到颜色序列上就变成若干段编号上升的区间

发现要按块的长度从小到大贪心，本质就是多重排列计数

然后就做完了😅

复杂度 O ( n 3 ) O(n^3) O(n3)

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define ull unsigned long long
using namespace std;
const int mod=998244353;
const int N=305;
int n;
string str;
int a[N],m;
ll dp[N][N];
ll fac[N],inv[N];
void add(ll &x,ll y){x=(x+y)%mod;
}
ll fpow(ll x,ll y=mod-2){ll z(1);for(;y;y>>=1){if(y&1)z=z*x%mod;x=x*x%mod;}return z;
}
void init(int n){fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;inv[n]=fpow(fac[n]);for(int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>str,init(n);int tot=0;for(int i=0;i<n-1;i++){if(str[i]=='R'){tot++;}else{a[++m]=tot;}}dp[0][0]=1;for(int i=0;i<=a[m];i++){for(int j=m;j>=0;j--){for(int k=0;k<=a[m];k++){if(dp[j][k]){for(int l=1;j+l<=m&&k+i*l<=a[j+l];l++){add(dp[j+l][k+i*l],dp[j][k]*inv[l]);}}}}}ll res=0;for(int i=0;i<=a[m];i++)add(res,dp[m][i]*fac[m]);cout<<(res+mod)%mod;
}