HDU4565(SummerTrainingDay05-C 矩阵快速幂)

So Easy!

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4673 Accepted Submission(s): 1539

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

根据条件可证(a-√b)ⁿ小于1，(a+√b)ⁿ向上取整即为求(a+√b)ⁿ + (a-√b)ⁿ，问题又转换为a^n+b^n的形式。

 1 //2017-08-05
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 #define ll long long
 7 
 8 using namespace std;
 9 
10 ll a, b, n;
11 ll p, q;
12 const int N = 5;
13 ll MOD;
14 
15 struct Matrix  
16 {  
17     ll a[N][N];  
18     int r, c; 
19 }ori, res;  
20 
21 void init()  
22 {  
23     memset(res.a, 0, sizeof(res.a));  
24     res.r = 1; res.c = 2;
25     res.a[1][1] = p;
26     res.a[1][2] = 2;
27     ori.r = 2; ori.c = 2;  
28     ori.a[1][1] = p;
29     ori.a[1][2] = 1;
30     ori.a[2][1] = -q;  
31     ori.a[2][2] = 0;  
32 }  
33 
34 Matrix multi(Matrix x, Matrix y)  
35 {  
36     Matrix z;  
37     memset(z.a, 0, sizeof(z.a));  
38     z.r = x.r, z.c = y.c;    
39     for(int i = 1; i <= x.r; i++) 
40     {  
41         for(int k = 1; k <= x.c; k++)      
42         {  
43             if(x.a[i][k] == 0) continue;
44             for(int j = 1; j<= y.c; j++)  
45                 z.a[i][j] = (z.a[i][j] + (x.a[i][k] * y.a[k][j]) % MOD + MOD) % MOD;  
46         }  
47     }  
48     return z;  
49 }  
50 
51 void Matrix_pow(int n)  
52 {  
53     while(n)  
54     {  
55         if(n & 1)  
56             res = multi(res, ori);  
57         ori = multi(ori, ori);  
58         n >>= 1;  
59     }  
60     printf("%lld
", res.a[1][1] % MOD);
61 }  
62 
63 int main()
64 {
65     while(scanf("%lld%lld%lld%lld", &a, &b, &n, &MOD)!=EOF){
66         p = 2*a;
67         q = a*a-b;
68         init();
69         if(n == 0)printf("2
");
70         else if(n == 1)printf("%lld
", p);
71         else Matrix_pow(n-1);
72     }
73 
74     return 0;
75 }

Source