[ An Ac a Day ^_^ ] hdu 4565 数学推导+矩阵快速幂

从今天开始就有各站网络赛了

今天是ccpc全国赛的网络赛

希望一切顺利可以去一次吉大希望还能去一次大连

题意：

很明确是让你求Sn=[a+sqrt(b)^n]%m

思路：

一开始以为是水题暴力了一发没过

上网看了一下才知道是快速幂

而且特征方程的推导简直精妙

尤其是共轭相抵消的构造真的是太看能力了

（下图转自某大神博客）

特征方程是C^2=-2*a*C+(a*a-b)

然后用快速幂求解

临时学了下矩阵快速幂

从这道题能看出来

弄ACM真的要数学好

这不是学校认知的高数线代概率分数

而是一种数学思维

能想得到什么公式会临场推导这种能力才是最重要的

学校考试卷子上的分数只能证明你考试的能力

分数再高没有数学思维也是没用的

从这样的题才能看出来一个人的数学到底好不好

我的路还很远……

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<math.h>
 5 #include<string.h>
 6 #include<string>
 7 #include<map>
 8 #include<set>
 9 #include<vector>
10 #include<queue>
11 #define M(a,b) memset(a,b,sizeof(a))
12 using namespace std;
13 typedef long long ll;
14 ll m;
15 struct matrix{
16     ll mt[2][2];
17     matrix mul(matrix a,matrix b){ //矩阵相乘
18         matrix c;
19         M(c.mt,0);
20         for(int i=0;i<2;i++)
21             for(int j=0;j<2;j++)
22                 for(int k=0;k<2;k++)
23                     c.mt[i][j]+=(a.mt[i][k]*b.mt[k][j])%m; //这里要模m 要不会因为溢出WA
24         return c;
25     }
26     matrix fast_pow(matrix a,ll mod){ //快速幂
27         matrix result;
28         for(int i=0;i<2;i++)
29             for(int j=0;j<2;j++)
30                 result.mt[i][j]=(i==j);
31         while(mod){
32             if(mod%2) result=mul(result,a);
33             a=mul(a,a);
34             mod/=2;
35         }
36         return result;
37     }
38 }mt;
39 int main(){
40     ll a,b,n;
41     while(scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&m)!=EOF){
42         mt.mt[0][0]=2*a;
43         mt.mt[0][1]=1;
44         mt.mt[1][0]=b-a*a;
45         mt.mt[1][1]=0;
46         mt=mt.fast_pow(mt,n-1);
47         ll ans=((2*a*mt.mt[0][0]+2*mt.mt[1][0])%m+m)%m; //这里取两次模因为第一次取模可能是负数
48         printf("%I64d
",ans);
49     }
50     return 0;
51 }
52 /*
53 
54 2 3 1 2013
55 2 3 2 2013
56 2 2 1 2013
57 
58 */