Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1729 Accepted Submission(s): 556
Problem Description
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!
Input
There are several test cases, each test case in one line contains four positive integers: a, b, n, m. Where 0< a, m < 215, (a-1)2< b < a2, 0 < b, n < 231.The input will finish with the end of file.
Output
For each the case, output an integer Sn.
Sample Input
2 3 1 2013 2 3 2 2013 2 2 1 2013
Sample Output
4 14 4
Source
此题的思路在于这儿....看图...
1 /*快速矩@ coder Gxjun*/
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5 __int64 ma[2][2]; //matrix
6 __int64 ans[2][2];
7 void init(__int64 a[][2])
8 {
9 int i;
10 for(i=0;i<2;i++)
11 a[i][i]=1; //E 设置为1
12 a[1][0]=0;
13 a[0][1]=0;
14 }
15 int main()
16 {
17 int a,b,m,n,i,j,k;
18 __int64 temp[2] ;
19 __int64 hop[2][2];
20 while(scanf("%d%d%d%d",&a,&b,&n,&m)!=EOF)
21 {
22 if(n==1)
23 {
24 printf("%I64d\n",(2*a)%m);
25 continue;
26 }
27 else if(n==2)
28 {
29 printf("%I64d\n",(2*(a*a+b))%m);
30 continue;
31 }
32 n-=2;
33 init(ans);
34 /*init(ma);*/
35 ma[0][0]=(2*a)%m;
36 ma[0][1]=(b-a*a)%m;
37 ma[1][0]=1;
38 ma[1][1]=0;
39 while(n>0)
40 {
41 if(n&1)
42 {
43 for(k=0;k<2;k++)
44 {
45 memset(temp,0,sizeof(temp));
46 for(i=0;i<2;i++)
47 {
48 for(j=0;j<2;j++)
49 {
50 temp[i]+=ans[k][j]*ma[j][i];
51 temp[i]%=m;
52 }
53 }
54 ans[k][0]=temp[0];
55 ans[k][1]=temp[1];
56 }
57 n--;
58 continue;
59 }
60 memset(hop,0,sizeof(hop));
61 for(k=0;k<2;k++)
62 {
63 for(i=0;i<2;i++)
64 {
65 for(j=0;j<2;j++)
66 {
67 hop[k][i]+=ma[k][j]*ma[j][i];
68 hop[k][i]%=m;
69 }
70 }
71 }
72 for(i=0;i<2;i++)
73 {
74 for(j=0;j<2;j++)
75 {
76 ma[i][j]=hop[i][j];
77 }
78 }
79 n>>=1;
80 }
81 __int64 gong=(2*((ans[0][1]*a)%m+(ans[0][0]*(a*a+b)%m)%m)%m)%m;
82 if(gong<0) gong=m+gong;
83 printf("%I64d\n",gong);
84 }
85 return 0;
86 }