So Easy!

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2286    Accepted Submission(s): 710

Problem Description

　　A sequence S

_n 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 S

_n.

　　You, a top coder, say: So easy! 

 

Input

　　There are several test cases, each test case in one line contains four positive integers: a, b, n, m. Where 0< a, m < 2

¹⁵, (a-1)

²< b < a

², 0 < b, n < 2

³¹.The input will finish with the end of file.

 

Output

　　For each the case, output an integer S

_n.

 

Sample Input

2 3 1 2013 2 3 2 2013 2 2 1 2013

 

Sample Output

4 14 4

 

挑战程序设计竞赛P268，关键是求初始矩阵：

an+1 = a*an+b*bn;

bn+1 = an+a*bn;

a[0][0],a[0][1]分别是公式1里面的系数，a和b;

a[1][0],a[1][1]分别是公式2里面的系数，1和a;

然后就是矩阵快速幂了：

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #define M(a,b) memset(a,b,sizeof(a)) 8 typedef long long LL; 9 10 using namespace std;11 12 13 long long a,b,n,m;14 15 struct matrix16 {17 LL mat[2][2];18 void init()19 {20 mat[0][0] = a;21 mat[0][1] = b;22 mat[1][0] = 1;23 mat[1][1] = a;24 }25 };26 27 matrix mamul(matrix aa,matrix bb)28 {29 matrix c;30 for(int i = 0;i<2;i++)31 {32 for(int j = 0;j<2;j++)33 {34 c.mat[i][j] = 0;35 for(int k = 0;k<2;k++)36 c.mat[i][j]+=(aa.mat[i][k]*bb.mat[k][j]);37 c.mat[i][j]%=m;38 }39 }40 return c;41 }42 43 matrix mul(matrix s, int k)44 {45 matrix ans;46 ans.init();47 while(k>=1)48 {49 if(k&1)50 ans = mamul(ans,s);51 k = k>>1;52 s = mamul(s,s);53 }54 return ans;55 }56 57 int main()58 {59 while(scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&m)==4)60 {61 matrix ans;62 ans.init();63 ans = mul(ans,n-1);64 printf("%I64d\n",(ans.mat[0][0]*2+m)%m);65 }66 return 0;67 }