暴力做法一点优化都没有的大常数代码直接过了

#include<bits/stdc++.h>
using namespace std;
long long Mod=10000;
long long fail[100010],n,t,m,a[100010];
long long qpow(long long di,long long mi){
	if(mi==0)
		return 1;
	if(mi==1)
		return di;
	long long tmp1=qpow(di,mi>>1),tmp2=qpow(di,mi&1);
	return tmp1*tmp1%Mod*tmp2%Mod;
}
int main(){
	cin>>n>>t;
	while(t--){
		cin>>m;
		for(int i=1;i<=m;i++)
			cin>>a[i];	
		long long ans=0;
		for(int i=1;i<=m;i++){
			int flag=1,cnt=i;
			for(int j=m-i+1;j<=m;j++){
				if(a[j]!=a[i-cnt+1]){
					flag=0;
					break;
				}
				cnt--;
			}
			if(flag)
				ans+=qpow(n,i),ans%=Mod;
		}
		if(ans<1000){
			long long cnt=0,tmp=ans;
			while(ans)
				cnt++,ans/=10;
			for(int i=1;i<=4-cnt;i++)
				cout<<"0";
			cout<<tmp<<"\n";
		}
		else
			cout<<ans<<"\n";
			
	}
}