题意简述

有一个空着的长度为\(n\)的字符串\(ans\)，再给出一个长度为\(m\)的序列\(a\)，现要在序列中每个元素\(a_i\)的位置开始都规定必须为一个给定的字符串\(s\)。问字符串\(ans\)的可能种类。

解法

主要考虑有可能\(a_i\)之间互相冲突导致直接输出\(0\)，于是我们需要快速判断当前字符串\(s\)的首与尾是否匹配。显然有两种可行解法，第一种是KMP，第二种是玄学的字符串哈希。但是写这篇题解的蒟蒻不想打KMP，于是就写了一个哈希。

这里的哈希其实只用单哈希即可，模数我一开始取成\(99844353\)，目测不是个质数，但是竟然过了QAQ，然后换成\(998244353\)(丝毫不怕被卡的样子)，结果果断被卡(WA on test 31)，于是果断使用了\(19260817\)，就A掉了。

再讲一下字符串哈希结束之后的判断答案的种类数的做法，我们直接统计满足\(a_{i+1}-a_{i}>len\)的\(a_{i+1}-a_{i}-len\)的个数之和即可，注意首尾的特殊处理。

然后我们设刚才统计的个数为\(cnt\)个，那么答案就是\(26^{cnt}\)，连快速幂都不用打，直接暴力乘即可，最后注意取模。

代码

\(ch\)数组是上文中的字符串\(s\)

\(p\)是本题规定的模数

\(MOD\)是哈希的模数，\(BASE\)是哈希的基数

\(getVal\)函数用于取出\([l,r]\)的哈希值

#include 
    
     #include 
     
      #define p 1000000007int read(){    int x = 0; int zf = 1; char ch = ' ';    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();    if (ch == '-') zf = -1, ch = getchar();    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}char ch[1000005];long long res[1000005];long long fac[1000005];const long long MOD = 9982442353ll;const long long prime = 431ll;const long long BASE = 131ll;void getHash(int n){    res[0] = 1; fac[0] = 1;    for (int i = 1; i <= n; ++i)        fac[i] = (fac[i - 1] * BASE) % MOD;    for (int i = 1; i <= n; ++i)        res[i] = (res[i - 1] * BASE + (ch[i] - 'A') * prime) % MOD;}inline long long getVal(int l, int r){    return ((res[r] - ((res[l - 1] * fac[r - l + 1]) % MOD) + MOD) % MOD);}int a[1000005];int main(){    int n = read(), m = read();    scanf("%s", ch + 1);     int len = strlen(ch + 1);    if (!m){        long long ans = 1;        for (int i = 1; i <= n; ++i)            (ans *= 26) %= p;        printf("%lld", ans);        return 0;    }    getHash(len);    for (int i = 1; i <= m; ++i){        a[i] = read();        if (a[i] + len - 1 > n){            puts("0");            return 0;        }        if (i > 1 && a[i - 1] + len > a[i]){            int x = a[i - 1] + len - a[i];            if (getVal(len - x + 1, len) != getVal(1, x)){                puts("0");                return 0;            }        }    }    int cnt = a[1] - 1;    for(int i = 1; i < m; i++){        if(a[i] + len < a[i + 1]){            cnt += a[i + 1] - a[i] - len;        }    }    cnt += n - a[m] - len + 1;    long long ans = 1;    for (int i = 1; i <= cnt; ++i)        (ans *= 26) %= p;    printf("%lld", ans);    return 0;}