禁止的回文子串 Dyslexic Gollum
UVA1633
一个长的回文串都可以由短的回文串拓展而来，只要短的回文在左右两端增加相同的字符即可。因此，在考虑长度为$N$的01串时，只要在从长度为1向$N$拓展的过程中，保证后$K$个字符不是回文串即可。
定义：
$dp[i][j]$为考虑长度为i的串的后$K$个字符组成的子串为$j$时的合法字符串的数量。$IsPalindrome[i][j]$为长度为$i$的字符串$j$是否为回文串。由于$K\leq 10$，小于$int$的32为并且为01串，可以用一个$int$来保存字符串$j$，进行状态压缩。
求IsPalindrome
初始化：
即0，1，00，11为回文串。
转移方程：
典型的中心拓展法，一个回文串如果左右各增加一个相同的字符，则形成的新字符串仍然是回文串。
求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
32int getState(int State, int Last) {
//如果State的长度大于等于K，则去掉最左边
if (State >= 1 << K - 1) {
State -= 1 << K - 1;
}
//往右边拓展一格
return State << 1 | Last;
}
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= (1 << K) - 1; ++j) {
//如果前一状态的合法数为0，就没必要继续了
if (dp[i - 1][j] == 0) {
continue;
}
//枚举最右边添加0还是1
for (int x = 0; x <= 1; ++x) {
//将j往右拓展一格
int&& CurState = getState(j, x);
///如果i的后K个字符往右移动一位组成了回文串，就跳过
if (i >= K && IsPalindrome[K][CurState]) {
continue;
}
//如果i的后K个字符加上x形成回文串，就跳过（为了防止K为偶数当前j长度为奇数的错误）
if (i >= K + 1 && IsPalindrome[K + 1][j << 1 | x]) {
continue;
}
//如果向右移动一位并且最右边为x时合法，累加方案数
dp[i][CurState] += dp[i - 1][j];
dp[i][CurState] %= mod;
}
}
}
值得注意的是这一段代码：1
2
3if (i >= K + 1 && IsPalindrome[K + 1][j << 1 | x]) {
continue;
}
如果当前j的状态为0010，$x$=0，则j往右一位变成0100，不是回文串，当是此时00100已经形成了回文串。因为回文串长度的奇偶有些差异，因此需要在向右判断一位。
AC代码：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
using namespace std;
constexpr static int inf = 0x3f3f3f3f;
constexpr static int mod = 1000000007;
int N, K;
int dp[401][(1 << 11) | 1];
bool IsPalindrome[12][(1 << 11) | 1]{ false };
//i=4 return 0110
int getBit(const int&i) {
return (1 << i - 1) - 2;
}
void InitPalindrome() {
IsPalindrome[1][0] = IsPalindrome[1][1] = true;
IsPalindrome[2][0] = IsPalindrome[2][3] = true;
for (int i = 3; i <= 11; ++i) {
for (int j = 0; j <= (1 << i) - 1; ++j) {
IsPalindrome[i][j] = IsPalindrome[i - 2][(j & getBit(i)) >> 1] && ((j >> i - 1) == (j & 1));
}
}
}
int getState(int State, int Last) {
if (State >= 1 << K - 1) {
State -= 1 << K - 1;
}
return State << 1 | Last;
}
int DP() {
memset(dp, 0x0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= (1 << K) - 1; ++j) {
if (dp[i - 1][j] == 0) {
continue;
}
for (int x = 0; x <= 1; ++x) {
int&& CurState = getState(j, x);
if (i >= K && IsPalindrome[K][CurState]) {
continue;
}
if (i >= K + 1 && IsPalindrome[K + 1][j << 1 | x]) {
continue;
}
dp[i][CurState] += dp[i - 1][j];
dp[i][CurState] %= mod;
}
}
}
int&& Ans = 0;
for (int i = 0; i <= (1 << K) - 1; ++i) {
Ans = (Ans + dp[N][i]) % mod;
}
return Ans;
}
int main() {
int T;
ios::sync_with_stdio(false);
cin >> T;
InitPalindrome();
for (int Case = 1; Case <= T; ++Case) {
cin >> N >> K;
cout << DP() << endl;
}
return 0;
}
