ARC089D - ColoringBalls

Posted on Edited on In

ARC089D - ColoringBalls

题目大意

有一排 \(n\) 个球，一开始都是白色的。

然后有 \(m\) 次操作，用一个字符串表示，若第 \(i\) 个字符为r/b则表示可以选择一段区间染成 红色/蓝色。

不能直接把一个白球染成蓝色。

求最终不同的球染色情况的个数 \(\mod 10^9+7\) 。


分析

下文视 \(n,m\) 同 阶。

分析最终态，总可以描述为若干连续的红蓝段，中间由白色分开。

如果确定了每一个红蓝段的长度和交错情况，然后再在 \(n\) 个位置里分配就能得到方案数，因此可以先忽略每一段的长度来进行考虑。

对于每一个红蓝段，可以分成两类：

  1. 只出现了红色，称这样的段为单一段。

  2. 出现了蓝色，不一定出现红色，称这样的段为复合段。

    考虑这样的段如何构造得到：

    1. 先染了一次红色
    2. 然后染了一次蓝色
    3. 接下来的每一次操作，无论染红色还是蓝色，均可以使得交替次数 \(+2\) 。

    而最终得到的段，交替段的两端的红色段可以为空。

为了包含到所有情况，并且不算重，构造方案时必然需要贪心地考虑。

可以先枚举有 \(a\) 个复合段， \(b\) 个单一段。

贪心地将前 \(a+b\) 个 r 操作用以新建一个段， \(a\) 个复合段对应着前 \(a\) 个 r。

然后再为每一个复合段贪心地匹配后面的第一个 b 操作，记作 \((pos_i,match_i),i\in[1,a]\) 。

那么对于剩下的 r/b，每一个操作均可以对于 \(a\) 个中的某一些进行，称这样的r/b为自由的。

对于每一个自由的b，设其位置为 \(j\) ，其能操作的段 \((pos_i,match_i)\) 必然满足 \(pos_i<j\) 。

对于每一个自由的r，设其位置为 \(j\) ，其能操作的段 \((pos_i,match_i)\) 必然满足 \(match_i<j\) 。

对于 \(a\) 个复合段，容易求得它们各自能得到的自由操作数量，记作 \(c_i\) ，显然 \(c_i\ge c_{i+1}\) 。

设每一个段被操作了 \(b_i\) 次，满足条件的方案只需要满足 \(c_i\ge \sum_{j=i} b_j\) 。

而我们只需考虑 \(b_i\ge b_{i+1}\) 的方案，因为这样的方案更容易被满足。

其次还需要考虑这 \(a+b\) 个段之间的相对顺序：

  1. \(b\) 个单一段等价，无顺序；
  2. \(a\) 个复合段根据 \(b_i\) 分类， \(b_i\) 相同的段之间等价，需要在方案中除掉个数的阶乘。
  3. 最终还需要将 \(a,b\) 两部分归并。

考虑倒着处理 \(dp_{i,j,k}\) 表示考虑了 \([i,a]\) 这些复合段， \(b_i=j\) ， \(\sum_{l=j} b_l=k\) 。

每次枚举一个 \(b_i\) 相同的段进行转移，即 \[ dp_{i,j,k}\leftarrow \sum_{d=1} \frac{1}{d!}\sum_{l=0}^{j-1} dp_{i+d,l,k+jd} \cdot [\ \forall p\in[0,d), k-jp\leq c_{i+p}] \] 可以在 \(j\) 这一维上前缀和优化，剩余的部分转移复杂度的一个上界为 \(O(n^3\ln n)\) 。

最终还需要将 \(a,b\) 两部分归并，并且将 \(n\) 个位置分配到每一个段中。

如果最终的方案额外加入了 \(i\) 个自由操作，则每一个段可以两类。

  1. 可以为空的段：
    • 每一个复合段两端的红色段；
    • 序列两端的白色段。
  2. 不能为空的段：
    • 每一个复合段中间的段；
    • 每一个单一段；
    • 每一个交替段之间的白色段。

这是一个简单的插板问题，可以用组合数在 \(O(1)\) 时间求解。

而需要枚举 \(O(n^2)\) 个 \(a,b\) ，每次需要 \(O(n^3\ln n)\) 的 \(\text{dp}\) ，故总复杂度为 \(O(n^5\ln n)\) 。

实际上这个上界非常松，可以随意通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) f|=IO=='-';
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const int N=72,INF=1e9+10,P=1e9+7;

int n,m,ans;
char s[N];
int Com[N*4][N*4],J[N],I[N];
ll qpow(ll x,ll k=P-2) {
    ll res=1;
    for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
    return res;
}
int R[N],mk[N],C[N],pos[N],c;
// R[i] 表示第i个复合段匹配的第一个b
// pos 表示每一个a出现的位置
// C[i] 表示每一个复合r之后的自由点个数
void Add(int &a,int b){
    a+=b,Mod1(a);
}
// 枚举 a 个复合段，b个单一段
void Calc(int a,int b) {
    if(!a && !b) { ans++; return; }
    rep(i,1,a) if(R[i]>m) return;
    rep(i,1,m) mk[i]=0;
    rep(i,1,a) mk[R[i]]=1;
    rep(i,1,a+1) C[i]=0;
    // 为自由的b找到能放置的第一个复合点
    rep(i,1,m) if(s[i]=='b' && !mk[i]) {
        drep(j,a,1) if(pos[j]<i) {
            C[j]++;
            break;
        }
    }
    // 为自由的r找到能放置的第一个复合点
    rep(i,a+b+1,c) {
        drep(j,a,1) if(R[j]<pos[i]) {
            C[j]++;
            break;
        }
    }
    static int dp[N][N][N];
    // dp[i][j]表示上一个放了i个，一共放了j个，处理掉分母的count[i]!
    // 每次枚举一段，且都放了k个
    dp[a+1][0][0]=1;
    drep(i,a-1,1) C[i]+=C[i+1];
    drep(i,a,1) {
        rep(j,0,C[i]) rep(k,0,C[i]) dp[i][j][k]=0;
        rep(k,1,C[i]) {
            int up=C[i];
            rep(j,i,a) {
                up=min(up-k,C[j]-k);
                if(up<0) break;
                rep(d,0,min(up,C[j+1])) Add(dp[i][k][d+k*(j-i+1)],1ll*dp[j+1][min(k-1,C[j+1])][d]*I[j-i+1]%P);
            }
        }
        dp[i][0][0]=I[a-i+1];
        rep(j,1,C[i]) rep(k,0,C[i]) Add(dp[i][j][k],dp[i][j-1][k]);
    }
    rep(i,0,C[1]) if(dp[1][C[1]][i]) {
        // 计算可以为0的段数以及不可以为0的段数
        int c1=2+a*2; // 两端的黑段，每一个非单一段两端的红段
        int c2=a+b-1+a+i*2+b; // 中间的每一个黑段，每一个非单一段除了红段以外的段，每一个单一段
        if(c2>n) continue;
        ans=(ans+1ll*Com[n+c1-1][c1+c2-1]%P*J[a]%P*Com[a+b][a]%P*dp[1][C[1]][i])%P;
    }
}

int main() {
    rep(i,0,N*4-1) rep(j,*Com[i]=1,i) Com[i][j]=Com[i-1][j]+Com[i-1][j-1],Mod1(Com[i][j]);
    rep(i,*J=1,N-1) J[i]=1ll*J[i-1]*i%P;
    I[N-1]=qpow(J[N-1]);
    drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P;
    n=rd(),m=rd();
    scanf("%s",s+1);
    int j=1;
    rep(i,1,m) if(s[i]=='r') {
        pos[++c]=i;
        cmax(j,i),j++;
        while(j<=m && s[j]!='b') j++;
        R[c]=j;
    }
    rep(a,0,c) rep(b,0,c-a) if((a+b)*2-1<=n) {
        Calc(a,b);
    }
    printf("%d\n",ans);
}