这题在比赛的时候不知道怎么做，后来看了别人的解题报告，才知道公式sn=(a+sqrt(b))^n+(a-sqrt(b))^n;
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<string>
using namespace std;
struct ma
{
__int64 a[][];
void init()
{
a[][]=a[][]=;
a[][]=a[][]=;
}
};
int mod;
ma mul(ma a,ma b)
{
ma ans;
int i,j,k;
for(i=;i<;i++)
for(j=;j<;j++)
{
ans.a[i][j]=;
for(k=;k<;k++)
ans.a[i][j]=(ans.a[i][j]%mod+((a.a[i][k]%mod)*(b.a[k][j]%mod)%mod))%mod;
}
return ans;
}
ma pows(ma a,__int64 n)
{
ma ans;
ans.init();
while(n)
{
if(n&)
ans=mul(ans,a);
n>>=;
a=mul(a,a);
}
return ans;
}
int main()
{
int a,b,n;
__int64 sum,q,s;
while(scanf("%d%d%d%d",&a,&b,&n,&mod)!=EOF)
{
ma p,ans;
s=*a%mod;
p.a[][]=s;
p.a[][]=(b-a*a)%mod;
p.a[][]=;
p.a[][]=;
q=((*a*a)%mod+*b%mod)%mod;
ans=pows(p,n-);
sum=(((ans.a[][]%mod)*(q%mod))%mod+((ans.a[][]%mod)*(s%mod)))%mod;
if(sum<) sum=(sum+mod)%mod;
printf("%I64d\n",sum);
}
return ;
}