C++ 解法, 执行用时: 59ms, 内存消耗: 460K, 提交时间: 2021-08-29 22:39:49

#include<cstdio>
using namespace std;
typedef long long ll;
int n,k,mod,g;
struct martix{
	int n;
	ll x[27][27];
	martix operator*(const martix &a)const{
		martix res;
		res.n=n;
		for(int i=0;i<n;++i)
			for(int j=0;j<n;++j){
				res.x[i][j]=0;
				for(int k=0;k<n;++k)
					res.x[i][j]+=x[i][k]*a.x[k][j]%mod;
				res.x[i][j]%=mod;
			}
		return res;
	}
	void init(int y){
		n=y;
		for(int i=0;i<n;++i)
			for(int j=0;j<n;++j)
				x[i][j]=(i==j?1:0);
	}
};
ll fpow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)res=res*a%mod; 
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
martix fpow(martix a,ll b){
	martix res;res.init(a.n);
	while(b){
		if(b&1)res=res*a; 
		a=a*a;
		b>>=1;
	}
	return res;
}
int main(){
	int t;scanf("%d",&t);
	while(t--){
		scanf("%d%d%d%d",&n,&k,&mod,&g);
		ll ans=0;
		for(int d=1;d<=g;++d){
			if(d==1)ans=(ans+fpow(k+1,n))%mod;
			else{
				int tot=fpow(d,k);
				martix A;
				A.init(tot);
				for(int i=0;i<tot;++i){
					for(int j=0,x=1;j<k;++j,x*=d){
						int y=i/x%d;
						int z=i-x*y;
						y=(y+1)%d;
						z+=y*x;
						A.x[i][z]=1; 
					} 
				}
				A=fpow(A,n);
				ans=(ans+A.x[0][0])%mod;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}