hdu 5950 Recursive sequence

  题意：告诉你数列的递推公式为f(n+1)=f(n)+2*f(n-1)+(n+1)^4 以及前两项a,b；问第n项为多少，结果对2147493647取模。

  题解：有递推公式，马上应该就能想到矩阵快速幂；但是，以前写过的矩阵快速幂绝大都是常数做系数的，如果这题是f(n+1)=f(n)+2*f(n-1)这样那倒蛮简单的构造个2*2矩阵很快能做出来；而后面接个(n+1)^4这种当时就gg了，，不知该如何下手。后来拜读了大佬的代码后才恍然大悟，，=_=...

  对于(n+1)^4，展开来后就是n^4+4*n^3+6*n^2+4*n+1，以及(n+1)^3展开是n^3+3*n^2+3*n+1那么，根据这个公式就可以在矩阵相乘时由{f(n),f(n-1),n^4,n^3,n^2,n,1}递推出{f(n+1),f(n),(n+1)^4,(n+1)^3,(n+1)^2,(n+1),1}。  故可构造7*7矩阵：

                                                　　　　　　　　　　

     用矩阵快速幂求其n-2次方的结果后，再与矩阵{ f(2), f(1), 2^4, 2^3, 2^2, 2, 1 } 即可得到第n项。

ac代码：

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include <set>
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 const int inf=0x3f3f3f3f;
13 const double PI=acos(-1.0);
14 const double EPS=1e-8;
15 using namespace std;
16 typedef long long ll;
17 typedef pair<int,int> P;
18 
19 const ll mod=2147493647LL;
20 ll n,a,b;
21 typedef struct Marix
22 {
23     ll m[7][7];
24 } Marix;
25 Marix p = {1, 1, 0, 0, 0, 0, 0,
26            2, 0, 0, 0, 0, 0, 0,
27            1, 0, 1, 0, 0, 0, 0,
28            4, 0, 4, 1, 0, 0, 0,
29            6, 0, 6, 3, 1, 0, 0,
30            4, 0, 4, 3, 2, 1, 0,
31            1, 0, 1, 1, 1, 1, 1
32           };
33 Marix mul(Marix a,Marix b)
34 {
35     Marix c;
36     memset(c.m,0,sizeof(c.m));
37     for(int k=0; k<7; k++)
38         for(int i=0; i<7; i++)
39             for(int j=0; j<7; j++)
40                 c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod;
41     return c;
42 }
43 Marix pow_mod(Marix a,ll n)
44 {
45     Marix c;
46     for(int i=0; i<7; i++) for(int j=0; j<7; j++) c.m[i][j]=(i==j); //将c初始化为单位矩阵
47     //
48     for(; n; n>>=1)
49     {
50         if(n&1) c=mul(c,a);
51         a=mul(a,a);
52     }
53     return c;
54 }
55 void debug()
56 {
57 }
58 int main()
59 {
60     //freopen("input.txt","r",stdin);
61     //debug();
62     int T;
63     scanf("%d",&T);
64     while(T--)
65     {
66         scanf("%I64d%I64d%I64d",&n,&a,&b);
67         //
68         if(n==1)
69         {
70             cout<endl;
71             continue;
72         }
73         else if(n==2)
74         {
75             cout<endl;
76             continue;
77         }
78         //
79         Marix c=pow_mod(p,n-2);
80         ll ans=b*c.m[0][0]%mod+a*c.m[1][0]%mod;
81         ans+=16*c.m[2][0]+8*c.m[3][0]+4*c.m[4][0]+2*c.m[5][0]+c.m[6][0];
82         cout<endl;
83     }
84     return 0;
85 }
矩阵·快速幂

相关

标签