「SWTR-04」D Lining up
Alex_Wei
·
·
题解
Upd on 2020.10.7 修改一个小 typo。
题面传送门
Subtask 1：没啥好说的，记得开 long long。
Subtask 2：我们设问号的个数为 y，明显可以 2^y 暴力枚举问号是 \texttt{B\ or\ G}，计算出符合条件的情况数 x，答案就是 \large\frac{x}{2^y}，对 10^9+7 取模就行了。
时间复杂度：上界为 \mathcal{O(2^n)}。
- 接下来我们只讨论如何得到符合条件的情况数，前置知识：基础 DP。
Subtask 3：考虑 4 维 DP，f_{i,j,k,p} 表示前 i 位同学组成了 j 个 \texttt{GB}，k 个 \texttt{BG}，且当前位为 p（p=0 时为 \texttt{G}，p=1 时为 \texttt{B}）共有多少种情况，其中 i\in[1,n],j\in[1,n],k\in[1,n],p\in\{0,1\}。转移方程：
f_{i,j,k,0}=\begin{cases}0&s_i=\texttt{B}\\f_{i-1,j,k-1,1}&s_{i-1}=\texttt{B},s_i=\texttt{G}\\f_{i-1,j,k,0}&s_{i-1}=\texttt{G},s_i=\texttt{G}\\f_{i-1,j,k-1,1}+f_{i-1,j,k,0}&s_{i-1}=\texttt{?}\ ,s_i=\texttt{G}\end{cases}
最后枚举所有 $j,k$，如果 $j\times a-k\times b\ge m$，情况数就加上 $f_{n,i,j,0}+f_{n,i,j,1}$。
时间复杂度：$\mathcal{O(n^3)}$。
---
- 下文中，我们设 $x$ 为 $\texttt{GB}$ 的个数，$y$ 为 $\texttt{BG}$ 的个数。
Subtask $4$：其实这个 Subtask 是引导你走向正解的（逃
该 Subtask 就是在求最后的 $x-y\ge m$ 共有多少种情况。
这就不由地让我们提出一个问题：$x$ 与 $y$ 到底有什么关系？它们的差的范围是多少？
如果你想到这个问题，那么恭喜你，你离 AC 本题不远了！
现在的你只需要挖掘出这个性质：**在任何时刻，$|x-y|\leq 1$**。
应该挺好理解的吧 qwq，举个例子：如果现在有一个转折点 $\texttt{BG}$，那么下一个转折点一定不可能是 $\texttt{BG}$，因为中间一定经过一个 $\texttt{GB}$ 的转折。说的再通俗一点，就是 $\texttt{BG.....BG}$ 的省略号中一定有 $\texttt{GB}$ 的转折。
所以这就引出了 Subtask $5$ 的解法：仍然是 $4$ 维 DP，$f_{i,j,k,p}$ 表示前 $i$ 位同学，$x$ 的值为 $j$，**$x-y+1$ 的值为 $k$**，且当前位为 $p$（$x,y,p$ 的定义上文有说明）共有多少种情况，其中 $i\in[1,n],j\in[1,n],k\in\{0,1,2\},p\in\{0,1\}$。
这样，时间复杂度就被我们压缩成了 $\mathcal{O(n^2)}$。
注意到空间只有 $8\texttt{MB}$，滚动数组优化一下即可。
感谢验题人 [Isaunoya](https://www.luogu.com.cn/user/96580) 倾情赞助的 std，因为出题人写的 std 锅掉了。
```cpp
// powered by c++11
// by Isaunoya
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7 ;
int qpow(int x , int y) {
int res = 1 ;
for( ; y ; y >>= 1 , x = 1ll * x * x % mod)
if(y & 1)
res = 1ll * res * x % mod ;
return res ;
}
int inv(int x) {
return qpow(x , mod - 2) ;
}
int n , a , b ;
long long m ;
const int maxn = 2020 + 0202 ;
int arr[maxn] ;
int dp[2][maxn][3][2] ;
// i
// j * a
// -(j-k+1)
void del(int & x) {
if(x >= mod) x -= mod ;
}
void addGB(int i) {
int p = i & 1;
for(int j = 0 ; j < i ; j ++)
for(int k = 0 ; k < 2 ; k ++) {
dp[p][j][k][0] += dp[p ^ 1][j][k + 1][1] ;
del(dp[p][j][k][0]) ;
}
}
void addBG(int i) {
int p = i & 1;
for(int j = 1 ; j < i ; j ++)
for(int k = 1 ; k < 3 ; k ++) {
dp[p][j][k][1] += dp[p ^ 1][j - 1][k - 1][0] ;
del(dp[p][j][k][1]) ;
}
}
void addBB(int i) {
int p = i & 1;
for(int j = 0 ; j < i ; j ++)
for(int k = 0 ; k < 3 ; k ++) {
dp[p][j][k][1] += dp[p ^ 1][j][k][1] ;
del(dp[p][j][k][1]) ;
}
}
void addGG(int i) {
int p = i & 1;
for(int j = 0 ; j < i ; j ++)
for(int k = 0 ; k < 3 ; k ++) {
dp[p][j][k][0] += dp[p ^ 1][j][k][0] ;
del(dp[p][j][k][0]) ;
}
}
int main() {
// code begin.
cin >> n >> m >> a >> b ;
for(int i = 1 ; i <= n ; i ++) {
char c ;
cin >> c ;
if(c == '?') arr[i] = 2 ;
if(c == 'B') arr[i] = 1 ;
if(c == 'G') arr[i] = 0 ;
}
if(arr[1] < 2) dp[1][0][1][arr[1]] = 1 ;
else dp[1][0][1][1] = dp[1][0][1][0] = 1 ;
for(int i = 2 ; i <= n ; i ++) {
for(int j = 0 ; j < i ; j ++)
for(int k = 0 ; k < 3 ; k ++)
dp[i & 1][j][k][0] = dp[i & 1][j][k][1] = 0;
// 0 - G
if(arr[i] == 0 && arr[i - 1] == 0) addGG(i) ;
if(arr[i] == 0 && arr[i - 1] == 1) addGB(i) ;
if(arr[i] == 0 && arr[i - 1] == 2) addGG(i) , addGB(i) ;
// 1 - B
if(arr[i] == 1 && arr[i - 1] == 0) addBG(i) ;
if(arr[i] == 1 && arr[i - 1] == 1) addBB(i) ;
if(arr[i] == 1 && arr[i - 1] == 2) addBB(i) , addBG(i) ;
// 2 - ?
if(arr[i] == 2 && arr[i - 1] == 0) addGG(i) , addBG(i) ; // ?G
if(arr[i] == 2 && arr[i - 1] == 1) addBB(i) , addGB(i) ; // ?B
if(arr[i] == 2 && arr[i - 1] == 2) { // ??
addBG(i) , addBB(i) ;
addGB(i) , addGG(i) ;
}
}
int cnt = 0 ;
for(int i = 1 ; i <= n ; i ++)
if(arr[i] == 2) ++ cnt ;
int ans = 0 ;
for(int j = 0 ; j <= n ; j ++)
for(int k = 0 ; k < 3 ; k ++) {
if(1ll * j * a - 1ll * (j - k + 1) * b >= m) {
ans += dp[n & 1][j][k][0] ;
del(ans) ;
ans += dp[n & 1][j][k][1] ;
del(ans) ;
}
}
cout << 1ll * ans * inv(qpow(2 , cnt)) % mod << '\n' ;
return 0 ;
// code end.
}
```