[ exttt{Description}
]
- 编程找出符合下列条件的字符串：①字符串中仅包含 0 和 1 两个字符；②字符串的长度为 n ；③字符串中不包含连续重复三次的子串。
[ exttt{Solution}
]
-
考虑到，将一个串延长至 (3) 倍，就成了连续重复三次的串。
-
于是我们枚举长度在 (frac{n}{3}) 以内的所有 (0/1) 串，将其延长至 (3) 倍，插入 (AC) 自动机中，显然这样插入，所有串的总长是可以承受的，在每个串的结尾，我们给他打上 (danger) 标记，也就是说我们不能匹配到包含 (danger) 标记的任意串。
-
考虑 (dp) 。
-
设 (f(i,j)) 表示：考虑到 (0/1) 串的前 (i) 位，在 (AC) 自动机上的节点为 (j) 时的字符串数量。
-
采用刷表法的方式进行 (dp) ，考虑当前的节点 (j) ，若 (j) 有 (danger) 标记，则不能计算 (j) 的贡献，否则不难得到如下转移：
[f(i+1,Next[j][0]) +=f(i,j)
]
[f(i+1,Next[j][1])+=f(i,j)
]
- 最后答案即为 (sumlimits_{danger(i)= ext{false}}f(n,i))
[ exttt{Code}
]
#include <bits/stdc++.h>
const long maxn = 40;
const long times = 3;
const long maxNode = 400000;
long n;
long head, last;
long next[maxNode][2], danger[maxNode], pre[maxNode], self[maxNode], fa[maxNode];
long list[maxNode + 1];
long f[2][maxNode + 1], ans;
void in() {
scanf("%ld", &n);
}
void prepare() {
long i, j, k, l, whe, now, s, t;
for (i = 1; i <= maxNode; i++) next[i][0] = next[i][1] = danger[i] = 0;
last = 0;
head = 0;
fa[0] = 0;
for (i = 1; i <= n / 3; i++) {
for (j = 0; j < (1 << i); j++) {
whe = head;
for (k = 1; k <= times; k++) {
for (l = 1; l <= i; l++) {
now = (j >> (l - 1)) & 1;
if (!next[whe][now]) {
self[next[whe][now] = ++last] = now;
fa[last] = whe;
}
whe = next[whe][now];
}
}
danger[whe] = 1;
}
}
s = 0;
t = 1;
list[1] = head;
while (s < t) {
whe = list[++s];
for (i = 0; i <= 1; i++)
if (next[whe][i])
list[++t] = next[whe][i];
if (fa[whe]) {
pre[whe] = next[pre[fa[whe]]][self[whe]];
} else
pre[whe] = head;
}
for (i = 1; i <= t; i++) {
whe = list[i];
for (j = 0; j <= 1; j++)
if (!next[whe][j])
next[whe][j] = next[pre[whe]][j];
danger[whe] |= danger[pre[whe]];
}
}
void dp() {
long i, j, k, now, pre;
for (i = 0; i <= last; i++) f[0][i] = 0;
f[0][0] = 1;
now = 0;
pre = 1;
for (i = 0; i < n; i++) {
now = 1 - now;
pre = 1 - pre;
for (j = 0; j <= last; j++) f[now][j] = 0;
for (j = 0; j <= last; j++) {
if (!danger[j]) {
f[now][next[j][0]] += f[pre][j];
f[now][next[j][1]] += f[pre][j];
}
}
}
ans = 0;
for (i = 0; i <= last; i++) {
if (!danger[i]) {
ans += f[now][i];
}
}
}
void work() {
prepare();
dp();
}
void out() {
std::cout << ans << std::endl;
}
int main() {
in();
work();
out();
return 0;
}
[ exttt{Thanks} exttt{for} exttt{watching}
]