CF#508 Div2 F. Wrap Around
? 解题记录 ? ? Codeforces ? ? KMP ? ? 动态规划 ?    2018-09-18 09:18:41    486    0    0

You are given a binary string ss.

Find the number of distinct cyclical binary strings of length nn which contain ss as a substring.

The cyclical string tt contains ss as a substring if there is some cyclical shift of string tt, such that ss is a substring of this cyclical shift of tt.

For example, the cyclical string "000111" contains substrings "001", "01110" and "10", but doesn't contain "0110" and "10110".

Two cyclical strings are called different if they differ from each other as strings. For example, two different strings, which differ from each other by a cyclical shift, are still considered different cyclical strings.

Input

The first line contains a single integer nn (1n401≤n≤40) — the length of the target string tt.

The next line contains the string ss (1|s|n1≤|s|≤n) — the string which must be a substring of cyclical string tt. String ss contains only characters '0' and '1'.

Output

Print the only integer — the number of distinct cyclical binary strings tt, which contain ss as a substring.

Examples
input
Copy
20
output
Copy
3
input
Copy
4
1010
output
Copy
2
input
Copy
20
10101010101010
output
Copy
962
Note

In the first example, there are three cyclical strings, which contain "0" — "00", "01" and "10".

In the second example, there are only two such strings — "1010", "0101".

## 时间复杂度：O(n^3)

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
LL dp[55][55][2], ans;
int n, m, fail[55], trans[55][2], v;
char s[55];

int GetF(int x, char c) {
while(~x && s[x + 1] != c) x = fail[x];
return ~x ? (x + 1) : 0;
}

void build() {
int p;
fail[0] = -1;
for(register int i = 1; i <= m; ++i) {
p = fail[i - 1];
while(~p && s[p + 1] != s[i]) p = fail[p];
if(~p) fail[i] = p + 1; else fail[i] = 0;
}
for(register int i = 0; i <= m; ++i) {
trans[i][0] = GetF(i, '0');
trans[i][1] = GetF(i, '1');
}
}

int main() {
scanf("%d", &n);
scanf("%s", s + 1);
m = strlen(s + 1);
build();
for(register int st = 0; st <= m; ++st) {
memset(dp, 0, sizeof(dp));
dp[0][st][0] = 1;
for(register int i = 0; i < n; ++i) {
for(register int j = 0; j <= m; ++j) {
v = trans[j][0];
dp[i + 1][v][v == m] += dp[i][j][0];
dp[i + 1][v][1] += dp[i][j][1];
v = trans[j][1];
dp[i + 1][v][v == m] += dp[i][j][0];
dp[i + 1][v][1] += dp[i][j][1];
}
}
ans += dp[n][st][1];
}
printf("%I64d", ans);
return 0;
}

486 人读过

0 条评论