51nod 1126 求递推序列的第N项(mod与%的区别+矩阵快速幂解递推问题）

1126 求递推序列的第N项

基准时间限制：1 秒空间限制：131072 KB 分值: 10 难度：2级算法题

关注

取消关注

有一个序列是这样定义的：f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

给出A，B和N，求f(n)的值。

Input

输入3个数：A,B,N。数字之间用空格分割。(-10000 <= A, B <= 10000, 1 <= N <= 10^9)

Output

输出f(n)的值。

Input示例

3 -1 5

Output示例

6

这题用暴力递推完美超时，大数据的递推自然首选矩阵快速幂。先构造一个矩阵：【f[n] f[n-1]】=【f[n-1] f[n-2]】 * {A  1}
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 {B  0}
然后运用矩阵快速幂模板，并注意下mod与%的区别（代码里有讲）

 1 //mod运算与%运算是有区别的，这也是这题的一个坑：
 2 //mod运算得到的数一定是非负数，而%则不一定
 3 //所以在最终结果小于0时，累加7直到非负
 4 #include <iostream>
 5 using namespace std;
 6 typedef long long ll;
 7 struct matrix
 8 {
 9     ll m[2][2];
10 };
11 matrix mul(matrix X,matrix Y)
12 {
13     matrix ans;
14     for(int i=0;i<2;i++)
15         for(int j=0;j<2;j++)
16         {
17             ans.m[i][j]=0;
18             for(int k=0;k<2;k++)
19                 ans.m[i][j]=(ans.m[i][j]+X.m[i][k]*Y.m[k][j])%7;
20         }
21     return ans;
22 }
23 matrix pow(matrix X,ll n)
24 {
25     matrix ans;
26     ans.m[0][0]=1;
27     ans.m[0][1]=0;
28     ans.m[1][0]=0;
29     ans.m[1][1]=1;
30     while(n)
31     {
32         if(n&1)
33             ans=mul(ans,X);
34         X=mul(X,X);
35         n>>=1;
36     }
37     return ans;
38 }
39 int main()
40 {
41     ios::sync_with_stdio(false);
42     ll a,b,n;
43     cin>>a>>b>>n;
44     matrix ans,X;
45     ans.m[0][0]=1;
46     ans.m[0][1]=1;
47     X.m[0][0]=a;
48     X.m[0][1]=1;
49     X.m[1][0]=b;
50     X.m[1][1]=0;
51     ans=mul(ans,pow(X,n-2));
52     while(ans.m[0][0]<0)
53         ans.m[0][0]+=7;
54     cout<<ans.m[0][0]<<endl;
55     return 0;
56 }

View Code