CF1038F Wrap Around

发表于 | 阅读数

给定一个字符串$S$，只包含$’0’$和$’1’$两个字符，求有多少长度为$n$的字符串$T$，满足以$T$为循环节的无限循环字符串包含$S$。 注意，哪怕在循环后相同，写出来不同的字符串$T$仍算不同的字符串$T$。例如$10$和$01$算不同的字符串$T$。

正着要考虑循环好几次，就很麻烦。

正难则反，我们需要的不包含，只需要头尾相连不包含即可不包含。

枚举前缀已经匹配到了$S$的前$[0,|S|),suf$,$dp[k][i][j]$表示从已经构造到地$k$个单词，并且从已经有的前缀匹配到$j$,原本匹配到了$i$。最后我要保证匹配到原本匹配到了$suf$即后缀有$suf$,答案是$\sum_{i} dp[n][suf][i]$。

  • 这里问题就是正难则反。不能匹配放到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
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

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 40 + 10;
const int mod = 1e9 + 7;

const int N_AC = 2e3;

ll dp[N][N][N];
struct ACAM
{
    int scnt;
    int nxt[N_AC][2], fail[N_AC];

    int root;

    int Newnode()
    {
        int pos = ++scnt;
        fail[pos] = 0;
        memset(nxt[pos], 0, sizeof(nxt[pos]));
        return pos;
    }
    void insert(char *t)
    {
        int len = strlen(t);
        int tmp = root;
        for (int i = 0; i < len; i++)
        {
            int id = t[i] - '0';
            if (!nxt[tmp][id])
                nxt[tmp][id] = Newnode();
            tmp = nxt[tmp][id];
        }
    }
    void build()
    {
        queue<int> q;
        for (int i = 0; i < 2; i++)
        {
            int tmp = nxt[root][i];
            if (tmp)
            {
                q.push(tmp);
                fail[tmp] = root;
            }
        }
        while (!q.empty())
        {
            int x = q.front();
            q.pop();

            for (int i = 0; i < 2; i++)
            {
                int tmp = nxt[x][i];
                if (tmp)
                {
                    q.push(tmp);
                    fail[tmp] = nxt[fail[x]][i];
                }
                else
                {
                    nxt[x][i] = nxt[fail[x]][i];
                }
            }
        }
    }
    ll solve(int n)
    {
        ll ans = 1ll << n;
        for (int i = 0; i < scnt; i++)
        {
            memset(dp, 0, sizeof(dp));
            dp[0][0][i] = 1;
            for (int j = 0; j < n; j++)
                for (int x = 0; x < scnt; x++)
                    for (int y = 0; y < scnt; y++)
                        for (int k = 0; k < 2; k++)
                        {
                            int a = nxt[x][k], b = nxt[y][k];
                            if (a == scnt || b == scnt)
                                continue;
                            dp[j + 1][a][b] += dp[j][x][y];
                        }
            for (int j = 0; j < scnt; j++)
                ans -= dp[n][i][j];
        }
        return ans;
    }
} t;

char s[N];
int main()
{
    int n;
    cin >> n;
    scanf("%s", s);
    t.insert(s);
    t.build();
    cout << t.solve(n) << endl;
}