把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF106D Coloring Bracket
题目大意：给你一个合法的括号串（范围为700），你要对他们涂色，可以涂成红和蓝，同一组括号只能且必须有一边涂色，涂色完了之后相邻的括号不能有相同的染色。

解：

由于括号之间的约束条件只与整体有关，所以很容易想到区间的问题。
很容易注意到本题的区间有两种情况：区间的左右两个括号是一组，这个时候两边必须有一且只有一边染色，也就是4种情况；而如果左右两个括号不是同一组，那么这个时候就有9种情况了（3^2）。
一个区间的转移中，如果左右并非同一组，说明它是由多个左右在同一组的区间合并得到的，这样问题就转化成了分治题目，该区间的状态转移相当于多个区间的合法状态合并，而合并的规则自然就是上面的9种情况的搭配了，已经能想到代码的长度了。
如果左右同一组，那么只要递推到他们更里面的状态然后转移就行。
边界是形如()的区间，显然他们只能返回前四种状态，且dp值为1，通过提前记录下括号对应的位置可以保证分治处理的区间永远是合法区间。
括号长度只有700，主要复杂度集中在9种情况的状态转移以及中间的区间合并，合并的时候向右推进的同时要记录最左边的括号状态，这样这个9又翻了一倍，代码又更加乱了。
想了无数种简写的方法还是写到了200行，很难想像是1900分的D题，让我码不得一个小时。
用分治解决区间问题的代表，当你无法直接通过遍历的n2复杂度来解决区间问题的时候应该会经常用到（主要是左边界和又边界同时需要处理，而且区间的合并并非只有左右合并，像本题中还有里外合并）。

代码

代码
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define inc(i,a,n) for(ll i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
using namespace std;
ll dp[701][701][9],with[701],dpt[701][9][9],le[3][3],re[3][3];
stack<ll> stk;
vector<ll> ban[9];
void dac(int start, int end) {
	if (with[start] == end) {
		if (start + 1 == end) {
			inc(i, 0, 4)dp[start][end][i] = 1;
			return;
		}
		else {
			int left = start + 1, right = end - 1;
			dac(left, right);
			ll s = 0;
			inc(i, 0, 9)s += dp[left][right][i];
			s %= mdl;
			dp[start][end][0] = (s - dp[left][right][0] - dp[left][right][5] - dp[left][right][7]+(ll)3*mdl)%mdl;
			dp[start][end][1] = (s - dp[left][right][1] - dp[left][right][5] - dp[left][right][8]+(ll)3*mdl)%mdl;
			dp[start][end][2] = (s - dp[left][right][2] - dp[left][right][6] - dp[left][right][8]+(ll)3*mdl)%mdl;
			dp[start][end][3] = (s - dp[left][right][3] - dp[left][right][6] - dp[left][right][7]+(ll)3*mdl)%mdl;
		}
	}
	else {
		vector<pll> segs;
		inc(i, start, end + 1) {
			pll p;
			p.first = i, p.second = with[i];
			dac(i, with[i]);
			segs.push_back(p);
			i = with[i];
		}
		int siz = segs.size();
		//cout << siz << endl;
		inc(i, 0, 9)dpt[0][i][i] = dp[segs[0].first][segs[0].second][i];
		inc(i, 1, siz) {
			int l = segs[i].first, r = segs[i].second;
			inc(j, 0, 9) {	
				if (l + 1 == r && j >= 4)break;
				inc(k, 0, 9) {
					inc(fr, 0, 9) {
						
						int flag = 0;
						if (ban[j].size()) {
							inc(b, 0, 3)
								if (ban[j][b] == fr)flag = 1;
						}
						if (flag == 0) {
							dpt[i][j][k] += dpt[i - 1][fr][k]*dp[l][r][j]%mdl;
						}
						dpt[i][j][k] %= mdl;
						
					}
				}
			}
		}
		dp[start][end][0] = 0;
		inc(i, 0, 3)
			inc(j, 0, 3)
			dp[start][end][0] += dpt[siz - 1][re[2][j]][le[0][i]];
		dp[start][end][0] %= mdl;
	
		dp[start][end][1] = 0;
		inc(i, 0, 3)
			inc(j, 0, 3)
			dp[start][end][1] += dpt[siz - 1][re[0][j]][le[2][i]];
		dp[start][end][1] %= mdl;
	
		dp[start][end][2] = 0;
		inc(i, 0, 3)
			inc(j, 0, 3)
			dp[start][end][2] += dpt[siz - 1][re[2][j]][le[1][i]];
		dp[start][end][2] %= mdl;
	
		dp[start][end][3] = 0;
		inc(i, 0, 3)
			inc(j, 0, 3)
			dp[start][end][3] += dpt[siz - 1][re[1][j]][le[2][i]];
		dp[start][end][3] %= mdl;
	
		dp[start][end][4] = 0;
		inc(i, 0, 3)
			inc(j, 0, 3) {
				dp[start][end][4] += dpt[siz - 1][re[2][j]][le[2][i]];
			}
		dp[start][end][4] %= mdl;
	
		dp[start][end][5] = 0;
		inc(i, 0, 3)
			inc(j, 0, 3)
			dp[start][end][5] += dpt[siz - 1][re[0][j]][le[0][i]];
		dp[start][end][5] %= mdl;
	
		dp[start][end][6] = 0;
		inc(i, 0, 3)
			inc(j, 0, 3)
			dp[start][end][6] += dpt[siz - 1][re[1][j]][le[1][i]];
		dp[start][end][6] %= mdl;
	
		dp[start][end][7] = 0;
		inc(i, 0, 3)
			inc(j, 0, 3)
			dp[start][end][7] += dpt[siz - 1][re[1][j]][le[0][i]];
		dp[start][end][7] %= mdl;
	
		dp[start][end][8] = 0;
		inc(i, 0, 3)
			inc(j, 0, 3)
			dp[start][end][8] += dpt[siz - 1][re[0][j]][le[1][i]];
		dp[start][end][8] %= mdl;
		inc(i, 0, siz) {
			inc(j, 0, 9) {
				inc(k, 0, 9) {
					dpt[i][j][k] = 0;
				}
			}
		}
	}
	inc(i, 0, 9) {
	//	cout << "dp." << start << "." << end << "."<<i<<" = " << dp[start][end][i] << endl;
	}
}
void init() {
	ban[0].push_back(1), ban[0].push_back(5), ban[0].push_back(8);
	ban[2].push_back(3), ban[2].push_back(6), ban[2].push_back(7);
	ban[5].push_back(1), ban[5].push_back(5), ban[5].push_back(8);
	ban[6].push_back(3), ban[6].push_back(6), ban[6].push_back(7);
	ban[7].push_back(1), ban[7].push_back(5), ban[7].push_back(8);
	ban[8].push_back(3), ban[8].push_back(6), ban[8].push_back(7);
	le[0][0] = 0, le[0][1] = 5, le[0][2] = 7;
	le[1][0] = 2, le[1][1] = 6, le[1][2] = 8;
	le[2][0] = 1, le[2][1] = 3, le[2][2] = 4;
	re[0][0] = 1, re[0][1] = 5, re[0][2] = 8;
	re[1][0] = 3, re[1][1] = 6, re[1][2] = 7;
	re[2][0] = 0, re[2][1] = 2, re[2][2] = 4;
}
int main() {
	cfast;
	init();
	string str;
	cin >> str;
	int n = str.length();
	inc(i, 1, n + 1) {
		if (str[i - 1] == '(')stk.push(i);
		else {
			int t = stk.top();
			with[t] = i;
			with[i] = t;
			stk.pop();
		}
	}
	dac(1, n);
	ll res = 0;
	inc(i, 0, 9) {
		res += dp[1][n][i];
		res %= mdl;
	}
	cout << res;
}//((()