# 矩阵类

struct Mat{
	int **a;
	int r,c;
	Mat(const int &r,const int &c):r(r),c(c){
		a=new int * [r];
		for(int i=0;i<r;++i)
			a[i]=new int [c]();
	}
	Mat(const int &r,const int &c,const int &x):Mat(r,c){
		for(int i=0;i<r;++i)
			a[i][i]=x;
	}
	Mat(const Mat &b):Mat(b.r,b.c){
		for(int i=0;i<r;++i)
			memcpy(a[i],b[i],sizeof(int)*c);
	}
	Mat operator * (const Mat &b)const{
		Mat res(r,b.c);
		for(int i=0;i<r;++i)
			for(int j=0;j<c;++j)
				for(int k=0;k<b.c;++k)
					(res[i][k]+=a[i][j]*b[j][k])%=P;
		return res;
	}
	int* operator [] (const int &x){
		return a[x];
	}
	const int* operator [] (const int &x)const{
		return a[x];
	}
	friend Mat pow(Mat a,int b){
		Mat res(a.r,a.r,1);
		for(;b;b>>=1,a=a*a)
			if(b&1) res=a*res;
		return res;
	}
};

# ABC305G 代码

#include<cstdio>
#include<cstring>
#include<bitset>
#include<iostream>
#define int long long
const int S=32;
const int P=998244353;
struct Mat{
	int **a;
	int r,c;
	Mat(const int &r,const int &c):r(r),c(c){
		a=new int * [r];
		for(int i=0;i<r;++i)
			a[i]=new int [c]();
	}
	Mat(const int &r,const int &c,const int &x):Mat(r,c){
		for(int i=0;i<r;++i)
			a[i][i]=x;
	}
	Mat(const Mat &b):Mat(b.r,b.c){
		for(int i=0;i<r;++i)
			memcpy(a[i],b[i],sizeof(int)*c);
	}
	Mat operator * (const Mat &b)const{
		Mat res(r,b.c);
		for(int i=0;i<r;++i)
			for(int j=0;j<c;++j)
				for(int k=0;k<b.c;++k)
					(res[i][k]+=a[i][j]*b[j][k])%=P;
		return res;
	}
	int* operator [] (const int &x){
		return a[x];
	}
	const int* operator [] (const int &x)const{
		return a[x];
	}
	friend Mat pow(Mat a,int b){
		Mat res(a.r,a.r,1);
		for(;b;b>>=1,a=a*a)
			if(b&1) res=a*res;
		return res;
	}
};
long long M,N;
char a[130],len[130];
Mat T(S,S),F(S,1),G(S,1);
bool contain(int a,int lena,int b,int lenb){
	for(int i=0;i<=lena-lenb;++i,a>>=1)
		if((a^(a>>lenb<<lenb))==b)
			return true;
	return false;
}
bool check(int s,int lens){
	for(int i=1;i<=M;++i)
		if(contain(s,lens,a[i],len[i]))
			return false;
	return true;
}
signed main(){
	scanf("%lld%lld",&N,&M);
	for(int i=1;i<=M;++i){
		char s[6],j;
		scanf("%s",s);
		for(j=0;s[j];++j)
			a[i]=a[i]<<1|(s[j]=='b');
		len[i]=j;
	}
	if(N<=5){
		int ans=0;
		for(int s=0;s<(1<<N);++s)
			ans+=check(s,N);
		printf("%d\n",ans);
		return 0;
	}
	for(int s=0;s<32;++s){
		if(check(s<<1,6))
			T[(s<<1)&31][s]=1;
		if(check(s<<1|1,6))
			T[(s<<1|1)&31][s]=1;
		if(check(s,5))
			F[s][0]=1;
	}
	G=pow(T,N-5)*F;
	int ans=0;
	for(int i=0;i<S;++i)
		(ans+=G[i][0])%=P;
	printf("%lld\n",ans);
	return 0;
}
更新于 阅读次数