g(i)=k*i+b; 0<=i<n
f(0)=0
f(1)=1
f(n)=f(n-1)+f(n-2) (n>=2)
求f(b) +f(k+b) +f(2*k+b) +f((n-1)*k +b) 之和
Sample Input
2 1 4 100 // k b n MOD
2 0 4 100
Sample Output
21
12
矩阵A 相当于
1 1 f（2） f(1)
1 0 f（1） f(0)
| 1 1| ^b | f(b+1) f(b)|
mat^b =|1 0 | = | f(b) f(b-1)|
求f（n） 就是求矩阵A的n次幂 再取第1行第2列的元素
要求的东西可化成 A^b*( I + A^k + (A^k)^2 + .... + (A^k)^(N-1) )
矩阵ans1 = A^b
矩阵B = A^k
矩阵C =
B I
O I
C的n次幂后 再取右上的小矩阵 就是I+B+B^2....+B^(n-1) 赋给ans2
ans1 * ans 再取第1行第2列的元素 就是最终答案
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# define LL long long
using namespace std ; LL MOD ; struct Matrix
{
LL mat[][];
}; Matrix mul(Matrix a,Matrix b, int n)
{
Matrix c;
for(int i=;i<n;i++)
for(int j=;j<n;j++)
{
c.mat[i][j]=;
for(int k=;k<n;k++)
{
c.mat[i][j]=(c.mat[i][j] + a.mat[i][k]*b.mat[k][j])%MOD;
}
}
return c;
}
Matrix pow_M(Matrix a,int k , int n)
{
Matrix ans;
memset(ans.mat,,sizeof(ans.mat));
for (int i=;i<n;i++)
ans.mat[i][i]=;
Matrix temp=a;
while(k)
{
if(k&)ans=mul(ans,temp,n);
temp=mul(temp,temp,n);
k>>=;
}
return ans;
} int main ()
{
//freopen("in.txt","r",stdin) ;
Matrix A ;
A.mat[][] = A.mat[][] = A.mat[][] = ;
A.mat[][] = ;
int n , k , b ;
while(cin>>k>>b>>n>>MOD)
{
int i ,j ;
Matrix ans1 , ans2;
ans1 = pow_M(A,b,) ; Matrix B , C ;
B = pow_M(A,k,) ;
memset(C.mat,,sizeof(C.mat));
for (i = ; i < ; i++) //扩展成4 * 4的矩阵C
{
for (j = ; j < ; j++)
{
C.mat[i][j] = B.mat[i][j] ;
}
C.mat[+i][+i] = ;
C.mat[i][+i] = ;
}
ans2 = pow_M(C,n,) ; // 4*4 ans2.mat[][] = ans2.mat[][] ;
ans2.mat[][] = ans2.mat[][] ;
ans2.mat[][] = ans2.mat[][] ;
ans2.mat[][] = ans2.mat[][] ;
ans1 = mul(ans1,ans2,) ; cout<<ans1.mat[][]%MOD<<endl ;
} return ;
}