Des
给出一个配对的括号序列(如"(())()"、"()"等, ")()"、"(()"是不符合要求的 ),对该序列按以下方法进行染色:
1.一个括号可以染红色、蓝色或不染色
2.一对匹配的括号需要且只能将其中一个染色
3.相邻两个括号颜色不能相同(但可以都不染色)
求符合条件的染色方案数(对1000000007取模)
\(\texttt{Data Range:}\)
2<=序列长度<=700
Sol
跟今年 [[【题解】P7914 括号序列(CSP-S2021)|CSP-S T2]] 如出一辙。
一个区间有两种转移方式,一是 (())
,二是 ()...()
。对于第二种方式直接转移会算重。
所以要记一个 \(g_{i,j}\) 数组表示上一次转移是 (())
的括号序列的数列。然后在拼接 \(f_{i,j}\) 时,钦定左边是 \(g\),右边是 \(f\) 即可。原理相当于钦定从 \(i\) 匹配的右括号处转移。
注意需要记录首尾颜色,但这样会导致复杂度变成 \(O(350^3\times 81)\),需要尽可能的在代码中判断无效状态,并 continue
掉。
另一种方法是用记忆化搜索,不进入无效状态即可。
My code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 705, MD = 1e9 + 7;
inline int add(int a, int b) { return a + b >= MD ? a + b - MD : a + b; }
inline int mul(int a, int b) { return (long long)a * b % MD; }
inline void Add(int &a, int b) { a = add(a, b); }
inline void Mul(int &a, int b) { a = mul(a, b); }
int n, f[N][N][3][3], g[N][N][3][3], ok[N][N];
char s[N];
int main() {
scanf("%s", s + 1), n = strlen(s + 1);
for(int i = 1; i <= n; i++) {
int cnt = 0;
for(int j = i; j <= n; j++) {
if(s[j] == '(') ++cnt;
else --cnt;
if(cnt == 0) ok[i][j] = true;
}
}
for(int i = 1; i < n; i++)
if(s[i] == '(' && s[i + 1] == ')')
for(int k = 1; k <= 2; k++)
f[i][i + 1][0][k] = f[i][i + 1][k][0] = 1,
g[i][i + 1][0][k] = g[i][i + 1][k][0] = 1;
for(int len = 4; len <= n; len++) {
for(int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
if(s[i] != '(' || s[j] != ')' || !ok[i][j]) continue;
if(s[i + 1] == '(' && s[j - 1] == ')' && ok[i + 1][j - 1])
for(int k = 1; k <= 2; k++)
for(int q = 0; q < 3; q++)
for(int h = 0; h < 3; h++) {
if(h == k) continue;
Add(f[i][j][0][k], f[i + 1][j - 1][q][h]);
Add(g[i][j][0][k], f[i + 1][j - 1][q][h]);
Add(f[i][j][k][0], f[i + 1][j - 1][h][q]);
Add(g[i][j][k][0], f[i + 1][j - 1][h][q]);
}
for(int k = i + 1; k < j - 1; k++) {
if(s[k] != ')' || s[k + 1] != '(' || !ok[i][k] || !ok[k + 1][j]) continue;
for(int h = 0; h < 3; h++) for(int q = 0; q < 3; q++) {
if(!g[i][k][h][q]) continue;
for(int p = 0; p < 3; p++) for(int r = 0; r < 3; r++) {
if((q == p && q != 0) || !f[k + 1][j][p][r]) continue;
Add(f[i][j][h][r], mul(g[i][k][h][q], f[k + 1][j][p][r]));
}
}
}
}
}
int ans = 0;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
Add(ans, f[1][n][i][j]);
cout << ans << '\n';
return 0;
}