文件详细信息

下载本文件

本文件的大小为 1342 字节。

#include<algorithm>
#include<cstdio>
typedef long long ll;
const int maxn=500,maxm=500,maxq=300;
const int P=5,P2=25,inv[5]={-1,1,3,2,4};
ll qpow(ll a,int x,const ll P){
	ll ans=1;
	while(x){
		if(x&1)ans=ans*a%P;
		a=a*a%P;
		x>>=1;
	}
	return ans;
}
int n,m,q,a[maxm][maxn+maxq];
char str[maxm+1];
int gauss(){
	int i=0,pos=0;
	for(;pos<n;i++,pos++){
		while(pos<n){
			for(int j=i+1;j<m;j++)
				if(a[j][pos]>0){
					std::swap(a[i],a[j]);
					break;
				}
			if(a[i][pos])break;
			pos++;
		}
		if(pos>=n)return qpow(5,n-i,1000000007);
		for(int k=0;k<m;k++){
			if(k==i)continue;
			const int tmp=a[k][pos]*inv[a[i][pos]]%P;
			for(int j=pos;j<n+q;j++)a[k][j]=(P2+a[k][j]-tmp*a[i][j])%P;
		}
		const int tmp=inv[a[i][pos]];
		for(int j=pos;j<n+q;j++)a[i][j]=a[i][j]*tmp%P;
	}
	return qpow(5,n-i,1000000007);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%s",str);
		for(int j=0;j<m;j++)a[j][i]=str[j]-'a';
	}
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		scanf("%s",str);
		for(int j=0;j<m;j++)a[j][n+i]=str[j]-'a';
 	}
	int ans=gauss();
	for(int i=0;i<q;i++){
		bool flag=true;
		for(int j=0;j<m;j++){
			if(!a[j][n+i])continue;
			bool is_0=true;
			for(int k=0;k<n;k++)
				if(a[j][k]){
					is_0=false;
					break;
				}
			if(is_0){
				flag=false;
				break;
			}
		}
		printf("%d\n",flag?ans:0);
	}
	return 0;
}