[洛谷P1349] 广义斐波那契数列

复习矩阵乘法。

题目传送门

裸题、水题。

a[n] a[n-1] * p 1 = a[n+1] a[n]

q 0

做这道题主要是因为自己突发奇想，尝试用数列的特征根求出通项公式......

然后发现这个坑填不平了......

就乖乖的改用矩乘秒掉了。

 1 #include<cstdio>
 2 #define ll long long
 3 
 4 ll p,q,a1,a2,n,m;
 5 
 6 struct matrix
 7 {
 8     ll a[2][2];
 9 }x;
10 
11 ll mul(ll w,ll e)
12 {
13     ll ret=0;
14     while(e)
15     {
16         if(e&1)ret=(ret+w)%m;
17         w=(w+w)%m;
18         e>>=1;
19     }
20     return ret;
21 }
22 
23 matrix mul(matrix w,matrix e)
24 {
25     matrix ret;
26     for(int i=0;i<=1;i++)
27     {
28         for(int j=0;j<=1;j++)
29         {
30             ret.a[i][j]=0;
31             for(int k=0;k<=1;k++)
32             {
33                 ret.a[i][j]=(ret.a[i][j]+mul(w.a[i][k],e.a[k][j]))%m;
34             }
35         }
36     }
37     return ret;
38 }
39 
40 matrix ksm(matrix w,ll e)
41 {
42     matrix ret=w;
43     e--;
44     while(e)
45     {
46         if(e&1)ret=mul(ret,w);
47         w=mul(w,w);
48         e>>=1;
49     }
50     return ret;
51 }
52 
53 int main()
54 {
55     scanf("%lld%lld%lld%lld%lld%lld",&p,&q,&a1,&a2,&n,&m);
56     x.a[0][0]=p;
57     x.a[0][1]=1;
58     x.a[1][0]=q;
59     x.a[1][1]=0;
60     if(n==1)printf("%lld",a1);
61     else
62     {
63         x=ksm(x,n-1);
64         printf("%lld",(x.a[0][1]*a2%m+x.a[1][1]*a1%m)%m);
65     }
66     return 0;
67 }