题解 | #NIT的签到题#

注意到贡献是独立的，所以没必要纠结长度为 $mm$ 中有多少个模式串，而只用算模式串总共出现了多少次。考虑枚举模式串头的位置，那么接下来 $nn$ 个位置被固定，其他位置看限制任意填。发现这些都可以直接维护。没啥细节，比标算的矩阵快速幂正常了一万倍。时间复杂度 $O(nk\sigma \log )O(nk\backslash sigma\backslash log)$。

//2021.12.27 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=500+10;
namespace MAIN{
    int n,m,k;
    char str[N];
    map<int,int> fl;
    map<int,int> F;
    map<Pair,int> ban;
    map<int,int> G;
    int q[N];
    int inv[N];
    inline void MAIN(){
        n=read(),m=read(),k=read(),scanf("%s",str+1),inv[0]=inv[1]=1;
        for(res i=2;i<=26;i++)inv[i]=mul(inv[kcz%i],kcz-kcz/i);
        for(res i=1;i<=k;i++){
            res op=read(),x=read(),ch=gc();
            while(ch<'a'||ch>'z')ch=gc();
            for(res j=1;j<=n&&x-j+1>=1;j++)if(x+n-j<=m)F[x-j+1]=1;
            if(!op){
                for(res j=1;j<=n&&x-j+1>=1;j++)if(str[j]==ch&&x+n-j<=m)fl[x-j+1]=1;
                if(ban[mp(x,ch-'a')]==2){puts("0");return;}
                ban[mp(x,ch-'a')]=1;
            }
            else {
                for(res j=1;j<=n&&x-j+1>=1;j++)if(str[j]!=ch&&x+n-j<=m)fl[x-j+1]=1;
                if(ban[mp(x,ch-'a')]==1){puts("0");return;}
                for(res j=0;j<26;j++){
                    if(j==ch-'a')continue;
                    if(ban[mp(x,j)]==2){puts("0");return;}
                }
                ban[mp(x,ch-'a')]=2;
            }
            q[i]=x;
        }
        sort(q+1,q+k+1),k=int(unique(q+1,q+k+1)-q-1);
        res ans=0,sum=1;
        for(res i=1;i<=k;i++){
            res o=0;
            for(res j=0;j<26;j++){
                if(!ban[mp(q[i],j)])o++;
                else if(ban[mp(q[i],j)]==2){o=1;break;}
            }
            if(!o){puts("0");return;}
            G[q[i]]=o;
            sum=mul(sum,o);
        }
        sum=mul(sum,qpow(26,m-k));
        for(auto x:F){
            if(fl[x.fi])continue;
            res ret=sum;
            for(res i=1;i<=n;i++){
                res p=x.fi+i-1;
                if(!G[p])ret=mul(ret,inv[26]);
                else ret=mul(ret,inv[G[p]]);
            }
            add(ans,ret);
        }
        add(ans,mul(m-n+1-int(F.size()),mul(sum,qpow(inv[26],n))));
        printf("%d\n",mul(ans,qpow(sum)));
    }
}