题意

求构造出长度为 n 的满足不出现 A 的字符串的方案数。字符集为数字,|A|\le 20n\le 10^9

思路

考虑 dp。

定义状态 f_{i,j} 表示构造到第 i 位,匹配到 A 的第 j 位的方案数。不难发现答案即为 \displaystyle\sum_{j = 1}^{m – 1} f_{n, j}。我们可以列出如下的转移方程:

f_{i,j} = \sum_{0\le k\le 9 }f_{i – 1, p}

其中这个 p 比较离谱,我们需要不断跳 fail 来找到这个 p

乍一看这个式子貌似不太好优化的样子,我们换一种思路:考虑 [1, j – 1] 匹配之后怎么匹配到 j

f_{i, j} = \sum_{k = 1}^{m – 1}f_{i – 1, k} \times g_{k, j}

这个式子的意思就是:假设前 i – 1 位的后缀为 A_{1\cdots k},考虑有多少种加数字的方法可以使匹配了的 A_{1\cdots k} 变成 A_{1\cdots j},方法数即为 g_{k,j}。注意到一定有 k > j,即 A_{1\cdots j}A_{1\cdots k} + n 的后缀,其中 n 为加上的数。

那么这个 g 怎么求呢?我们可以在每一位 i 枚举添加的数 j,然后跳 fail 直到找到合法的位置 p,让 g_{i,p} 加一即可。

for (int i = 0; i < m; ++i)
{
    for (int j = '0'; j <= '9'; ++j)
    {
        int p = i;
        while (p && s[p + 1] != j)
            p = fail[p];
        if (s[p + 1] == j) ++p;
        ++g.a[i][p];
    }
}

接下来我们把所有的 f_{i,j} 看成一个列向量 F_i,我们只需要每次 F_{i} = F_{i – 1}\times G 就可以了。F_{0,0} = 0

#include <cstdio>
#include <cstring>

const int maxm = 25;
int n, m, mod, fail[maxm];
char s[maxm];

struct matrix
{
    int a[maxm][maxm];
    matrix()
    {
        memset(a, 0, sizeof a);
    }
    matrix operator*(matrix &b)
    {
        matrix ret;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < m; ++j)
                for (int k = 0; k < m; ++k)
                    ret.a[i][j] = (ret.a[i][j] + this->a[i][k] * b.a[k][j]) % mod;
        return ret;
    }
};

matrix pow(matrix a, int p)
{
    matrix ret;
    for (int i = 0; i <= m; ++i)
        ret.a[i][i] = 1;
    for (; p; p >>= 1)
    {
        if (p & 1)
            ret = ret * a;
        a = a * a;
    }
    return ret;
}

int main()
{
    scanf("%d %d %d", &n, &m, &mod);
    scanf("%s", s + 1);
    matrix f, g;
    f.a[0][0] = 1;
    for (int i = 2, j = 0; i <= m; ++i)
    {
        while (j && s[j + 1] != s[i])
            j = fail[j];
        if (s[j + 1] == s[i])
            ++j;
        fail[i] = j;
    }
    for (int i = 0; i < m; ++i)
    {
        for (int j = '0'; j <= '9'; ++j)
        {
            int p = i;
            while (p && s[p + 1] != j)
                p = fail[p];
            if (s[p + 1] == j) ++p;
            ++g.a[i][p];
        }
    }
    f = f * (g = pow(g, n));
    int ans = 0;
    for (int i = 0; i < m; ++i)
        (ans += f.a[0][i]) %= mod;
    printf("%d\n", ans);
    return 0;
}
最后修改日期: 2021年3月6日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。