C++11(clang++ 3.9) 解法, 执行用时: 136ms, 内存消耗: 608K, 提交时间: 2020-04-01 19:05:01

#include<cstdio>
#include<cstring>
typedef long long ll;
inline bool isdig(char c)
{
	return c>='0'&&c<='9';
}
inline char getch(void)
{
	static char buf[100000],*p1=buf,*p2=buf;
	if(p1!=p2) return *p1++;
	p1=buf;
	p2=p1+fread(buf,1,100000,stdin);
	return p1==p2?EOF:*p1++;
}
template<class T> inline void read(T &num)
{
	bool neg=false;
	char c=getch();
	num=(T)0;
	while(!isdig(c))
	{
		neg|=(c=='-');
		c=getch();
	}
	while(isdig(c))
	{
		num=num*10+c-'0';
		c=getch();
	}
	num=neg?-num:num;
	return;
}
template<class T> inline void write(T num)
{
	if(!num)
	{
		putchar('0');
		return;
	}
	static char c[25];
	int cnt=0;
	if(num<0)
	{
		putchar('-');
		num=-num;
	}
	while(num)
	{
		c[++cnt]=(num%10)+'0';
		num/=10;
	}
	while(cnt) putchar(c[cnt--]);
	return;
}
const int K=55;
ll p;
struct Martix
{
	ll val[K][K];
	void zero(void)
	{
		memset(val,0,sizeof(val));
		return;
	}
	void one(void)
	{
		zero();
		for(register int i=0;i<=K-5;++i)
		val[i][i]=1;
		return;
	 } 
	 Martix operator *(const Martix m)const
	 {
	 	Martix ret;
	 	ret.zero();
	 	for(int i=0;i<=K-5;++i)
	 	for(int j=0;j<=K-5;++j)
	 	for(register int k=0;k<=K-5;++k)
	 	ret.val[i][j]=(ret.val[i][j]+val[i][k]*m.val[k][j])%p;
	 	return ret;
	 }
}ans,mov;
Martix power(ll b)
{
	Martix ret;
	ret.one();
	for(;b;b>>=1)
	{
		if(b&1) ret=ret*mov;
		mov=mov*mov;
	}
	return ret;
}
int main()
{
	ll n,k,r;
	read(n);
	read(p);
	read(k);
	read(r);
	for(register int i=0;i<k;++i)
	{
		mov.val[i][i]++;
		mov.val[i][(i-1+k)%k]++;
	}
	ans=power(n*k);
	write(ans.val[r][0]);
	return 0;
}