[DP记录]AT3878 [ARC089D] ColoringBalls

**题意** ： 有 $n$ 个白色的小球排成一排，有一个长为 $k$ 的字符串 $s$。 接下来进行 $k$ 次操作。 对于第 $i$ 个操作，选择一段连续的小球（可以为空），若 $S[i]=\texttt{r}$ 则将这些球染成红色；若是 $S[i]=\texttt{b}$，则将它们染成蓝色。 由于染料的特性，不能直接用蓝色来染白色。 求在进行完所有操作后，所有小球的颜色序列可以有多少种。答案对 $10^9+7$ 取模。 $n,k\leq 70$ ，时限$\texttt{4s}$。 ------------ 首先考虑如何判定某种颜色序列是否能被生成。 观察连续的一段有色区间，可能分布为 红蓝红蓝...红蓝红。 考虑有怎样的构造方案，如下图 ：  不难发现，若有 $k$ 个蓝色段，则所需的染色次数为 $k+1$ 次，红色和蓝色的次数不定，在 $[1,k]$ 之间。 （特殊地，若没有蓝色，则只需染一次红色） 在此基础上，还有染色顺序的限制。 若我们决定染 $a$ 次蓝色，最好的方案是 ： 先染一次红色，再染 $a-1$ 段蓝色，然后染一大段蓝色，再在这段蓝色上染完剩下的红色。 这对操作序列的要求 ： 满足个数要求。且最前面是 $\texttt{r}$ ，第二个是 $\texttt{b}$ 。没了！ 接着考虑多段有色区间。 设有 $a$ 个纯红色段，以及 $c$ 个杂色段。 则在操作序列中取出 $c$ 个尽量靠前的子序列 $\texttt{r},\texttt{b}$ ，再取出 $a$ 个尽量靠前的 $\texttt{r}$。后者用于处理纯红色段。 然后，从左到右考虑，将第 $i$ 个 $\texttt{r},\texttt{b}$ 分给第 $i$ **大**的杂色段，并在后面取走想要的若干个操作。 若发现无球可取，则无解。 形式化地，记第 $i$ 个 $\texttt{r},\texttt{b}$ 后面剩余的操作数目为 $t_i$。 第 $i$ 个杂色段的内部段数和为 $s_i$。（**降序**） 则对于所有 $i$ ，都要满足 $t_i\geq \sum_{j=i}^cs_j$。 接下来考虑计数。 枚举 $a,c$ ，然后我们得到了 $t_{1\sim c}$。 先考虑在得到 $s$ 的情况下，如何计算颜色序列的方案数。 将每一个“颜色段”看做一个盒子。 我们发现，对于一个 $s_i$ ，会产生 $2s_i-1$ 个至少有一个球的颜色段，以及 $2$ 可以为空的颜色段（两端的红球）。 对于 $a$ ，会产生 $a$ 个至少有一个球的颜色段。 对于白色的部分，会产生 $a+c-1$ 个至少有一个球的颜色段，以及 $2$ 个可以为空的颜色段（两端的白球）。 综上，非空盒的个数为 $2\sum s_i+2a-1$ 个，而可空盒为 $2c+2$ 个。 总球数为 $n$ ，容易用组合数求出方案。 此外，杂色段和纯红色段之间的顺序也需要考虑。 首先是杂色段和纯红色段混合的方案数，显然为 $\dbinom{a+c}{a,c}$。 然后是杂色段内部顺序数，即 $s$ 序列的不同排列数，这个使用 $\rm DP$ 求解。 设 $dp[i,j,k]$ 表示填写了 $s_{i\sim c}$ ，目前 $\sum s=j$ ，且 $s_i=k$ 的方案数（不同排列数）。 枚举在 $s$ 中选多少个 $k$ ，则有转移 ： $$dp[i,j,k]=\sum\limits_{p\geq 1}\binom{c-i+1}{p}\sum\limits_{g<k}dp[i+p,j-pk,g]$$ 式子中 $\binom{c-i+1}{p}$ 是将 $p$ 个 $k$ 归并到目前的 $s$ 中的方案数。 要求 $j\leq t_i$ 且 $\forall p'\in[1,p],\ j-p'k\leq t_{i+p'}$。 最终的答案是 $dp[1,\_,\_]$ ，根据第二维的 $\sum s$ 计算贡献系数。 使用前缀和优化，即可做到 $O(n^3\log n)$。 算上枚举 $a,c$ 的复杂度，总复杂度为 $O(n^5\log n)$。由于常数非常小，可以轻松通过。 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxN 75 using namespace std; const int mod=1000000007; ll powM(ll a,int t=mod-2){ ll ret=1; while(t){ if (t&1)ret=ret*a%mod; a=a*a%mod;t>>=1; }return ret; } int fac[MaxN<<1],ifac[MaxN<<1]; ll C(int n,int m) {return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;} void Init(int n) { fac[0]=1; for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod; ifac[n]=powM(fac[n]); for (int i=n;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod; } int n,m,t[MaxN],p[MaxN],dp[MaxN][MaxN][MaxN]; char str[MaxN];bool vis[MaxN]; int calc(int a,int c) { for (int i=1;i<=m;i++)vis[i]=0; int cnt=0; for (int i=1;i<=m;i++) if (str[i]=='r'){ cnt++; if (cnt<=c){ bool fl=0; for (int j=i+1;j<=m;j++) if (str[j]=='b'&&!vis[j]) {vis[p[cnt]=j]=fl=1;break;} if (!fl)return 0; }if (cnt<=a+c)vis[i]=1; } if (cnt<a+c)return 0; for (int i=1;i<=c;i++){ t[i]=0; for (int j=p[i];j<=m;j++) t[i]+=(!vis[j]||str[j]=='b'); }t[c+1]=0; for (int k=0;k<=m;k++)dp[c+1][0][k]=1; for (int i=c;i;i--) for (int j=0;2*j+2*a-1<=n&&j<=t[i];j++){ for (int k=0;k<=m;k++)dp[i][j][k]=0; for (int k=1;k<=m;k++) for (int p=1;j-p*k>=0&&i+p<=c+1&&j-p*k<=t[i+p];p++) dp[i][j][k]=(dp[i][j][k]+1ll*ifac[p]*dp[i+p][j-p*k][k-1])%mod; for (int k=1;k<=m;k++)dp[i][j][k]=(dp[i][j][k]+dp[i][j][k-1])%mod; } int ans=0; for (int j=0;2*j+2*a-1<=n&&j<=t[1];j++){ int x=2*j+2*a-1,y=2*c+2; ans=(ans+C(n+y-1,x+y-1)*dp[1][j][m])%mod; }return 1ll*ans*C(a+c,a)%mod*fac[c]%mod; } int main() { scanf("%d%d%s",&n,&m,str+1); Init(n+m+5); int ans=0; for (int a=0;a<=m;a++) for (int c=0;a+2*c<=m;c++) ans=(ans+calc(a,c))%mod; printf("%d",ans); return 0; } ```