Article From:https://www.cnblogs.com/ljzalc1022/p/9064231.html

Given a legitimate sequence of parentheses, you can dye each parenthesis red or blue, one pair of parentheses and only one is dyed, and the adjacent parentheses do not dye the same color, and ask the number of legitimate staining schemes.

The state needs to preserve the color of the left and right bracket in the current area, and whether the left and right boundaries are updated by the same pair of brackets.

``````#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int mod = 1000000007;
char s[705];
int n;
int top, sta[705], match[705];
long long f[705][705][9];
void ModAdd(long long & x, long long y) {
x += y;
if(x >= mod) x-= mod;
}
long long DP(int l, int r, int k) {
int lcol = k / 3, rcol = k % 3;
if(r - l == 1) {
//      printf("%d %d %d\n", k, lcol, rcol);
if((lcol == 0) == (rcol == 0)) return 0;
return 1;
}
long long & res = f[l][r][k];
if(res != -1) return res;
res = 0;
if(match[l] == r) {
if((lcol == 0) == (rcol == 0)) return res;
for(int i = 0; i < 3; i++) {
if(i != 0 && lcol != 0 && i == lcol) continue;
for(int j = 0; j < 3; j++) {
if(j != 0 && rcol != 0 && j == rcol) continue;
ModAdd(res, DP(l + 1, r - 1, i * 3 + j));
}
}
}
else {
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
if(i != 0 && j != 0 && i == j) continue;
ModAdd(res, DP(l, match[l], lcol * 3 + i) *
DP(match[l] + 1, r, j * 3 + rcol) % mod);
}
}
}
//  printf("%d %d %d %d %lld\n", l, r, lcol, rcol, res);
return res;
}
int main() {
scanf("%s", s);
n = strlen(s);
for(int i = 0; i < n; i++) {
if(s[i] == '(') sta[top++] = i;
else match[sta[--top]] = i;
}
long long ans = 0;
memset(f, -1, sizeof(f));
for(int i = 0; i < 9; i++) ModAdd(ans, DP(0, n - 1, i));
cout << ans << endl;
return 0;
}``````