C++ 解法, 执行用时: 481ms, 内存消耗: 8092K, 提交时间: 2021-06-22 14:15:44

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 998244353
int i,j,k,n,m,t;
set<int> s,s2;
char sb[105];
map<int,map<int,int> >mp;
map<int,int> num,mp2;
ll tot=1,inv[50],res,tmp;
struct SB{
	int x,y;char z;
}sb2[505];
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}

int main(){
	inv[1]=1;for(int i=2;i<=30;i++){inv[i]=(M-M/i)*inv[M%i]%M;}
    ios::sync_with_stdio(0);
    cin>>n>>m>>t>>sb+1;
    for(i=1;i<=n;i++){sb[i]-='a'-1;}
    for(i=1;i<=t;i++){
    	cin>>sb2[i].x>>sb2[i].y>>sb2[i].z;
		k=sb2[i].y;sb2[i].z-='a'-1;
    	s.insert(k);
    	num[k]=26;
    	for(j=1;j<=26;j++){mp[k][j]=1;}
		for(j=max(1,k-n+1);j<=min(m-n+1,k);j++){s2.insert(j);}
	}
	for(i=1;i<=t;i++){
		k=sb2[i].y;
		if(sb2[i].x){
			for(j=1;j<=26;j++){
				if(j==sb2[i].z){continue;}
				if(mp[k][j]){num[k]--;mp[k][j]=0;}
			}
		}
		else{
			if(mp[k][sb2[i].z]){num[k]--;mp[k][sb2[i].z]=0;}
		}
		if(!num[k]){cout<<0;return 0;}
	}
	tot=ksm(26,m);
	for(auto i:s){tot=tot*inv[26]%M*num[i]%M;}
	tmp=tot*ksm(ksm(26,n),M-2)%M;
	res=tmp*(m-n+1)%M;
	for(auto i:s2){
		res=(res+M-tmp)%M;
		ll tmp2=tmp;
		for(j=i;j<i+n;j++){
			if(!num[j]){continue;}
			if(!mp[j][sb[j-i+1]]){goto aaa;}
			tmp2=tmp2*inv[num[j]]%M*26%M;
		}
		res=(res+tmp2)%M;
		aaa:;
	}
	//cout<<res<<' '<<tot<<end;
	cout<<res*ksm(tot,M-2)%M;
}