A sequence Sn is defined as:
Where a, b, n, m are positive integers.┌x┐is the ceil of x. For example, ┌3.14┐=4. You are to calculate Sn.
You, a top coder, say: So easy!
矩阵快速幂
#include<stdio.h>
#include<string.h>
#include<math.h>
typedef long long ll;
int mod; struct mat{
int r,c;
ll m[][]; //经测试最大开成590*590的 ll 型矩阵
mat(){}
mat(int r,int c):r(r),c(c){}
void clear(){
memset(m,,sizeof(m));
} mat operator+(mat a)const{
mat ans(r,c);
for(int i=;i<=r;i++){
for(int j=;j<=c;j++){
ans.m[i][j]=(m[i][j]+a.m[i][j])%mod;
}
}
return ans;
} mat operator*(mat a)const{
mat tmp(r,a.c);
int i,j,k;
for(i=;i<=tmp.r;i++){
for(j=;j<=tmp.c;j++){
tmp.m[i][j]=;
for(k=;k<=c;k++){
tmp.m[i][j]=(tmp.m[i][j]+(m[i][k]*a.m[k][j])%mod)%mod;
}
}
}
return tmp;
} mat operator^(int n)const{ //需要时可以用 ll n，注意运算符优先级比较低，多用括号；
mat ans(r,r),tmp(r,r);
memcpy(tmp.m,m,sizeof(tmp.m));
ans.clear();
for(int i=;i<=ans.r;i++){
ans.m[i][i]=;
}
while(n){
if(n&)ans=ans*tmp;
n>>=;
tmp=tmp*tmp;
}
return ans;
} void print()const{
for(int i=;i<=r;i++){
for(int j=;j<=c;j++){
printf("%lld",m[i][j]);
if(j==c)printf("\n");
else printf(" ");
}
}
} }; int main(){
ll a,b,n;
while(scanf("%lld%lld%lld%d",&a,&b,&n,&mod)!=EOF){
if(n==){
printf("%lld\n",(*a)%mod);
continue;
}
mat tmp(,),t(,);
tmp.m[][]=(*a)%mod;
tmp.m[][]=((b%mod-(a*a)%mod)%mod+mod)%mod;
tmp.m[][]=;
tmp.m[][]=;
t.m[][]=((*a)%mod)*a%mod+(*(b%mod))%mod;
t.m[][]=(*a)%mod;
t=(tmp^(n-))*t;
printf("%lld\n",t.m[][]);
}
return ;
}