2019安徽-省赛J题 密信


写在前面,
由于本人在ACM队伍中不是负责数论的, 本题在dp思想的基础上需要用到数论知识进行优化, 所以我们在这里只讲解dp思想的朴素算法(会T), 优化代码我就不讲了.


Problem

Portal


Meaning

求长度为n且其子串集合中含给定字串的方案数. (用给定字串去匹配长度为n的母串, 给定字串都能匹配上的话, 方案数++)
Notice: 子串一定连续。


Thoughts

对于这道题(暴力的话枚举母串26^n就直接炸了)。看到子串匹配问题我们会想到KMP, AC自动机, 由于匹配子串, 所以我们不必用到AC自动机, 用KMP就好。然后就是本题最难的地方了, 这种数据范围很大, 暴力枚举不出来并且四不像的题, 要么dp, 要么思维推公式(最后发现组合数学不行有重复), 就只能dp了。但是由于dp我们枚举状态的话, 5e13炸了, 所以我们需要用到考虑到是否可能用矩阵快速幂加速递推呢? 将n降成logn枚举状态, 时间复杂度就够了。


Solutions

状态表示与集合划分

这种字串匹配的dp问题, 见过了我们就知道状态怎么表示, 没见过就不知道. 这里我们枚举母串长度与母串当前位置匹配到了子串的哪一位, 用f[i][j]表示当考虑到母串的第i位时, 母串匹配到了子串的第j个数的方案数。
母串长度为n的所有方案, 我们可以根据它与子串的匹配数来划分。
答案 = 母串长度为n的所有方案数(全排列) - f[n][i] (0 < i < len, 未匹配完的方案数, 最多也就只能匹配len个字符), 剩下的就是answer了。
Notice: f[n][len]表示的是长度为n且后缀匹配完了子串(也就是从最后一个字母向前长度为len的字符串 == 子串这一种情况)的母串(不包含中间的包含子串的长度为n的母串)方案数, 所以f[n][len]并不是答案。我们应该用全排列数量减去所有不能匹配完(当中间匹配不完的方案将会被归到f[i + 1][0]里面去, 所以不能匹配完的方案一定是全的)的方案。

状态转移(根据最后加上这个字母(26个)最后产生的匹配数的不同划分长度为i + 1的字母串集合)

  1. f[i + 1][u] += f[i][j] (满足条件的j: j加上i的这个位置枚举的字母之后, 母串与子串匹配到第u个数)

Notices:

  • 0 <= i < n(因为状态转移方程f[i + 1][u], i + 1 <= n, i < n)。
  • 0 < u <= len, 0 <= j < len(u = j + 1, u <= len, j < len).
  • 母串长度可能为0, 所以状态不能表示成f[i - 1][j]
for(int j = 0 ; j <= len ; j ++ ) // 枚举当前匹配位置
    for(int k = 0 ; k < 26 ; k ++ ) // 在第i位上加什么字母
        ...

KMP匹配代码: 为什么当匹配到了就不用再往下看了?
在母串第i位之后加上一个字符, 这个字符:

  • 可能是子串的0 - len位, 使得已匹配到u - 1位的方案变成u位的方案, 使得f[i + 1][u]的方案数多上f[i][u - 1]的方案数, 其他的不加(26个字母每个字母唯一)。
  • 可能是非子串字母

Notice: j 不只是u - 1, 因为如果是非子串字母或跳位字母(现在只有匹配两位的串, 出现了子串第5位的字母且与第3位不同)的话, 会让所有i匹配到子串的任意位置的所有方案结束, 使得f[i + 1][0]需要加上f[i][j] (0 <= j <= len)的所有方案(只有f[i][0]有这种情况)。


  1. f[i + 1][j] = f[i][k] * g[k][j] (0 < k < len)

Notices:

  • 这个g数组只能为0, 1, 所以就相当于是我们第一个状态转移方程的一个变型。先处理k能加上哪些字符, 变成j匹配。

我们可以发现f数组的第一维的n很大, 1e12, 数组无法储存, 这时我们想到能否降维呢? (降维优化对时间复杂度无优化)
根据状态转移方程, 我们可以发现, 根据y总所讲的可降维条件, 我们可以发现是不行的, 因为本题的状态转移是无序的, 因为f[i][u]有可能是由f[i][u + k]转移过来的。


  1. 矩阵快速幂优化状态转移方程II的状态转移, 加速递推

Time complexity

设P的长度为m, $O(26 * n * m)$, 矩阵快速幂优化dp状态枚举之后, 时间复杂度为$O(26 * m^2 * logn)$。


O(nm) Code with equation I

#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 55;

ll T, n, m;
char str[N];
int ne[N];
ll f[200][N]; // 实际上题目所给的数据范围炸数组

int main ()
{
    cin >> T;
    while(T -- )
    {
        memset(ne, 0, sizeof ne);
        memset(f, 0, sizeof f);
        cin >> n >> m;
        cin >> str + 1;

        int len = strlen(str + 1);

        // KMP预处理next数组
        for(int i = 2, j = 0 ; i <= len ; ++ i)
        {
            while(j && str[i] != str[j + 1]) j = ne[j];
            if(str[i] == str[j + 1]) j ++ ;
            ne[i] = j;  //这里是ne[i]不是ne[j]
        }

        f[0][0] = 1;
        for(int i = 0 ; i <= n ; ++ i)
            for(int j = 0 ; j < len ; ++ j)
                for(int k = 0 ; k < 26 ; ++ k)
                {
                    int u = j; // 当前匹配到了子串的哪一个位置

                    // KMP 匹配代码
                    while(u && k != str[u + 1] - 'a') u = ne[u]; // KMP 当母串的当前的字母无法匹配子串的下一个字母时 -> 我们重新匹配(见下图1)
                    if(k == str[u + 1] - 'a') ++ u; // 能匹配
                    if(u < len) f[i + 1][u] = (f[i + 1][u] + f[i][j]) % m; // f[i][j]加上一个字母完成转换, 所以我们需要加上f[i][j]的所有方案数 只用算所有未匹配完的方案数
                }

        ll res = 1;
        for(int i = 1 ; i <= n ; i ++ )
            res = res * 26 % m;
        for(int i = 0 ; i < len ; ++ i)
            res = (res - f[n][i] + m) % m;

        cout << res << endl;
    }

    return 0;
}

图1


Accepted Code

Portal


类似题目: luogu GT考试, acwing 设计密码
拓展题目: hdu 2243(多子串 -> AC自动机), acwing 修复DNA


Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Previous
图的割边求法汇总(基准, 并查集, Tarjan算法)及代码实现 图的割边求法汇总(基准, 并查集, Tarjan算法)及代码实现
If you want to read this article, please go to About page, scan wechat or alipay QR code, pay 200 yuan and contact blogger through QQ, then you can get the passsword and read the article.
2020-06-28
Next 
2019安徽-省赛G题 括号序列 2019安徽-省赛G题 括号序列
If you want to read this article, please go to About page, scan wechat or alipay QR code, pay 200 yuan and contact blogger through QQ, then you can get the passsword and read the article.
  TOC