记录编号	85348	评测结果	AAAAAAAAAA
题目名称	[SRM 377] 外星语言	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2014-01-01 21:32:41	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<iomanip>
using namespace std;
typedef long long ll;
ll MOD;
const int SIZEN=4;
class MATRIX{
public:
	int n,m;//n行m列
	ll s[SIZEN][SIZEN];
	MATRIX(){//初始化为零
		m=n=0;
		memset(s,0,sizeof(s));
	}
	void print(void){//调试接口,输出矩阵
		cout<<"size:"<<n<<" "<<m<<endl;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++) cout<<s[i][j]<<" ";
			cout<<endl;
		}
	}
	void assign_one(int sn){//赋值为sn行的单位矩阵
		n=m=sn;
		for(int i=1;i<=n;i++) s[i][i]=1;
	}
};
MATRIX operator * (MATRIX a,MATRIX b){//矩阵乘法,结果对MOD取模
	MATRIX c;
	c.n=a.n;c.m=b.m;
	int i,j,k;
	for(i=1;i<=c.n;i++){
		for(j=1;j<=c.m;j++){
			c.s[i][j]=0;
			for(k=1;k<=a.m;k++){
				c.s[i][j]+=(a.s[i][k]*b.s[k][j])%MOD;
				c.s[i][j]%=MOD;
			}
			c.s[i][j]%=MOD;
		}
	}
	return c;
}
MATRIX quickpow(MATRIX a,ll n){//a^n,sn行/列
	MATRIX ans;ans.assign_one(a.n);
	while(n){
		if(n&1) ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
ll calc(int N,int K){
	MATRIX I,D;
	I.n=1,I.m=3;
	I.s[1][1]=1,I.s[1][2]=K+1,I.s[1][3]=1;
	D.n=D.m=3;
	D.s[1][1]=K,D.s[1][2]=0,D.s[1][3]=0;
	D.s[2][1]=1,D.s[2][2]=K,D.s[2][3]=0;
	D.s[3][1]=0,D.s[3][2]=1,D.s[3][3]=1;
	I=I*quickpow(D,N);
	return I.s[1][1];
}
class AlienLanguage{//topcoder的格式要求
public:
	int getNumberOfWords(int,int,int,int);
};
int AlienLanguage::getNumberOfWords(int P,int Q,int N,int M){
	MOD=M;
	long double s=calc(N,P)*calc(N,Q);
	while(s>1e18&&s>=MOD) s-=MOD;
	ll ans=(ll) s;
	ans=(ans-1+MOD)%MOD;
	return (int)ans;
}
int main(){
	freopen("alienlanguage.in","r",stdin);
	freopen("alienlanguage.out","w",stdout);
	AlienLanguage test;
	int P,Q,N,M;
	cin>>P>>Q>>N>>M;
	cout<<test.getNumberOfWords(P,Q,N,M)<<endl;
	return 0;
}