【题解】ARC089F ColoringBalls

Posted on

简要题意

有 $n$ 个白色小球排成一排, 一个长度为 $K$ 的染色序列 $S$ , 依次进行 $K$ 次操作.

第 $i$ 次操作选择一段连续的小球(可以为空) , 若 $S$ 中的第 $i$ 个字符是 $r$ 则把这段小球染成红色, 若是 $b$ 则染成蓝色.

由于染料特性, 不能直接用蓝色来染白色.

求最终有多少种可能的小球序列, 对 $10^9+7$ 取模.

$n,K \leqslant 70$ .

为方便, 用 R/B 表示球的序列的颜色, 用 r/b 表示染色序列中的颜色.

先考虑什么样的球的序列最终能被得到, 显然序列中的白色是从来没被染色过的, 所以可以按白色来分割成多个连续的段.

这些段又可以分成两类, 包含蓝色和不包含, 显然, 后者一个 r 即可搞定, 前者稍有些复杂, 让我们来分析一下.

连续的相同颜色可以缩在一起, 如果开头是蓝色的球, 我们不妨在其前面补一个红球, 末尾同理, 因为反正必须在这整个段上先染一遍红色才能操作.

所以现在我们考虑这样一种序列应该怎么得到, RBRBRB...BR . 手玩一下 RBRBRBR 的染色方案, 不难发现, 它能被长度为 $4$ 的以下染色序列得出.

  • rbrr
  • rbrb
  • rbbr
  • rbbb

很明显的发现, 最开始的两个元素都是 rb , 思考一下这是为什么, 很显然, 第一步只能染红色, 第二步再染红色没意义, 所以只能是蓝色, 所以这个结论很对.

这 $4$ 个序列显然是最优的了, 不会有比这个更短的序列了, 而对于更长的序列, 它们肯定包含 rb , 并且 rb 之后至少有 $2$ 个元素, 因此它们肯定没有这个长度为 $4$ 的序列来的优秀.

这时我们不妨大胆猜一个结论, 对于有 $B$ 个蓝色连续段的两色序列, 有用的序列长度为 $B+1$ , 并且开头的两个元素一定是 rb , 至于多出的染色无所谓, 反正可以染空集. 这个应该是个经典结论, 贪心证明.

因此假设我们分出来的两色序列有 $x$ 个, 它们每个中分别有蓝色 $c_1,c_2,\dots,c_x$ 个, 而对于只包含红色格子的段有 $y$ 个.

这样的话球的序列能被染出来当且仅当 $S$ 能够被拆分成 $x+y$ 个子序列(允许有字符未被选择) , 其中恰好有 $y$ 个 r , 对于其他的 $x$ 个也都是 rb 开头, 并且长度恰好为 $c_i+1$ .

这样我们可以贪心的判断一个序列是否可以被染出, 我们先贪心的选择最靠前的 $x$ 个 rb , 再从剩下的子序列中贪心的选出 $y$ 个 r , 然后我们对于此时的局面, 对每个 $i$ 求出 $[i,n]$ 中有多少个字符目前没有被用来染色, 设为 $sum_i$ , 然后我们将选出的 $x$ 个 rb 按 b 的位置从小到大排序, 设为 $end_i$ , 再将 $c$ 序列从大到小排序, 然后我们就贪心的将第一个 rb 分给最大的 $c$ 以此类推, 这样我们可以知道一段序列符合要求, 当且仅当 $\forall i, sum_{end_i} \geqslant \sum\limits_{j=i}^x{c_j-1}$ .

我们考虑枚举 $x,y$ , 然后按照上面的方式先贪心的选出 $x$ 个 rb 和 $y$ 个 r , 这样我们可以很快的知道 $sum_i$ 以及 $end_i$ , 然后我们考虑倒着 $dp$ , 设 $f_{i,j,k}$ 表示考虑了 $i \sim x$ 段中蓝色点的个数, 且目前 $\sum\limits_{j=i}^{x}{c_j-1} = j$ , $c_i=k$ , 有多少种两色段之间两两位置关系的可能二点方案数, 转移的时候带上组合数, 最外面就不用乘多重组合数了. 转移就枚举有多少个 $j$ 满足 $c_j = k$ , 设为 $p$ , 再枚举上一个不同的 $c$ 的值, 设为 $q$ , 那么转移就很显然了 $f_{i,j,k}=\sum\limits_{p}\sum\limits_{q}{f_{i+p,j-(k-1)p,q} \vdot \dbinom{x-i+1}{p}[q<k]}$ , 注意到 $q$ 可以直接前缀和优化掉, 而 $p$ 的枚举是调和级数, 这样单次 $dp$ 就是 $\mathcal{O}(n^3\ln{n})$ 的.

接下来考虑计算一次 $dp$ 对答案的贡献, 即如何用 $f_{1,j,k}$ 的值和 $x,y$ 来计算答案, 首先两色段之间的关系在 $dp$ 中已经计算过了, 而 $y$ 个纯色和 $x$ 个两色段之间的位置关系也就是一个组合数 $\dbinom{x+y}{x}$ , 接下来还需要考虑每个段中球的数量有多少种可能.

我们先假设每个连续段(指球的序列的颜色段)为一个盒子, 每个盒子必须装同色球, 那么不妨假设一个由 $c$ 个 B 构成的段它只有 BRBRBRB , 那么这样一定会有 $2c-1$ 个盒子, 每个盒子中至少由一个球, 而两边还能放一些 R , 因此还会产生两个可空的盒子, 而段与段之间还有 $x+y-1$ 个空隙, 这些空隙只能放白球且每个空至少放一个, 同理两边也是可放可不放, 所以也是两个可空盒子. 所以我们有 $A=2j+2x+2y-1$ 个必须放球的盒子, 和 $B=2x+2$ 个可空的盒子, 贡献就是 $\dbinom{n+B-1}{A+B-1}$ .

时间复杂度 $\mathcal{O}(n^5\ln{n})$ 常数很小, 可以通过.

启示 :

  • 对于求解由多少个序列能被得到的这一类问题, 不妨先考虑什么样的序列能被得到, 如果没有得到足够的性质(比如说如果每次操作由啥不同, 最后结果一定不同)之前, 最好不要从操作序列的时间轴入手 $dp$ .
  • 如果一些信息在 $dp$ 的过程中不能直接求得/计算 $dp$ 系数时需要用到这些信息, 那不妨先枚举它们, 这样 $dp$ 的时候系数就比较好求了.

代码

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
/************************************************
*Author        :  demonlover
*Created Time  :  2022.02.20.20:59
*Problem       :  ARC89D
************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pii;
#define DEBUG(x) cout << #x << " = " << x << "\n"
template <typename T>
inline bool read(T &x) {
	int f = 1,c = getchar();x = 0;
	while (!isdigit(c)) {if (c == 45)f = -1;c = getchar();}
	while (isdigit(c))x = (x<<3)+(x<<1)+(c^48),c = getchar();
	return x *= f,true;
}
template <typename T,typename... Args>
inline bool read(T &x,Args &...args) {
	return read(x) && read(args...);
}

namespace run {
	const int maxn = 1e2+10,maxc = 5e2+10;
	const int mod = 1e9+7;
	int c[maxc][maxc];
	char s[maxn];
	bool vis[maxn];
	int pos[maxn],suf[maxn],sum[maxn];
	int n,m,ans;
	inline void init() {
		for (int i = 0;i < maxc;++i) {
			c[i][0] = 1;
			for (int j = 1;j <= i;++j)
				c[i][j] = (c[i-1][j]+c[i-1][j-1])%mod;
		}
		return;
	}
	inline bool check(int x,int y) {
		memset(vis,false,sizeof(vis));
		int cnt1 = 0,cnt2 = 0;
		for (int i = 1;i <= m;++i) {
			if (s[i] == 'r') {
				if (cnt1 < x+y)cnt1++,vis[i] = true;
			}
			else if (cnt2 < x && cnt1 > cnt2)cnt2++,vis[i] = true,pos[cnt2] = i;
		}
		if ((cnt1 ^ x+y) || (cnt2 ^ x))return false;
		suf[m+1] = 0;
		for (int i = m;i;--i)suf[i] = suf[i+1]+(!vis[i]);
		memset(sum,0,sizeof(sum));
		for (int i = 1;i <= x;++i)sum[i] = suf[pos[i]];
		return true;
	}
	int f[maxn][maxn][maxn],sumf[maxn][maxn][maxn];
	inline void solve(int x,int y) {
		memset(sumf,0,sizeof(sumf));memset(f,0,sizeof(f));
		f[x+1][0][0] = 1;
		for (int i = 0;i <= n;++i)sumf[x+1][0][i] = 1;
		for (int i = x;i;--i)
			for (int j = 0;j <= sum[i];++j)
				for (int k = 1;k <= n;++k) {
					for (int p = 1;p*(k-1) <= j && p+i-1 <= x && j-(k-1)*p <= sum[i+p];++p)
						f[i][j][k] = (f[i][j][k]+1ll*c[x-i+1][p]*sumf[i+p][j-(k-1)*p][k-1]%mod)%mod;
					sumf[i][j][k] = (sumf[i][j][k-1]+f[i][j][k])%mod;
				}
		return;
	}
	inline bool main() {
		read(n,m);
		scanf("%s",s+1);
		init();
		for (int a = 0;a <= n;++a)
			for (int b = 0;a+b <= n;++b) {
				if (!a && !b)continue;
				if (!check(a,b))continue;
				solve(a,b);
				for (int s = 0;s <= sum[1];++s)
					for (int lst = 0;lst <= n;++lst)
						if (f[1][s][lst]) {
							int A = (2*s+a)+(a+b-1)+b,B = 2*a+2;
							ans = (ans+1ll*f[1][s][lst]*c[a+b][a]%mod*c[n+B-1][A+B-1]%mod)%mod;
						}
			}
		printf("%d\n",(ans+1)%mod);
		cerr<<1.0*clock()/CLOCKS_PER_SEC<<"\n";
		return 0;
	}
}

#define demonlover
int main() {
#ifdef demonlover
	freopen("ARC89D.in","r",stdin);
	freopen("ARC89D.out","w",stdout);
#endif
	return run :: main();
}