HDU 5950 Recursive sequence 【递推+矩阵快速幂】 (2016ACM/ICPC亚洲区沈阳站)

Recursive sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 249    Accepted Submission(s): 140

Problem Description

Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would stand in a line, while John writes two positive numbers a and b on a blackboard. And then, the cows would say their identity number one by one. The first cow says the first number a and the second says the second number b. After that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, and

Input

The first line of input contains an integer t, the number of test cases. t test cases follow.
Each case contains only one line with three numbers N, a and b where N,a,b <

Output

For each test case, output the number of the N-th cow. This number might be very large, so you need to output it modulo 2147493647.

Sample Input

2 3 1 2 4 1 10

Sample Output

85 369

Hint
In the first case, the third number is 85 = 2*1十2十3^4. In the second case, the third number is 93 = 2*1十1*10十3^4 and the fourth number is 369 = 2 * 10 十 93 十 4^4.

Source

2016ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）

Recommend

jiangzijing2015   |   We have carefully selected several similar problems for you:  5960 5959 5958 5957 5956

Statistic | Submit | Discuss | Note

题目链接：

　　http://acm.hdu.edu.cn/showproblem.php?pid=5950

题目大意：

　　F_i=F_i-1+2F_i-2+i⁴。给定F₁和F₂求F_n。

题目思路：

　　【递推+矩阵快速幂】

　　现场用算了1个多小时的公式过了。

　　主要还是我太菜。递推写的太少。

　　先考虑f(i)=f(i-1)+2f(i-2)，很容易写出递推矩阵

　　　　0 2

　　　　1 1

　　(i+1)⁴=i⁴+4i³+6i²+4i+1。

　　所以需要在递推矩阵种存下i的4 3 2 1 0次幂，以便推出(i+1)⁴，矩阵为

　　　　1 0 0 0 0

　　　　4 1 0 0 0

　　　　6 3 1 0 0

　　　　4 3 2 1 0

　　　　1 1 1 1 1

　　于是f={f_i-1,f_i,i⁴,i³,i²,i¹,i⁰}，将以上两个矩阵合并，即可推出{f_i,f_i+1,(i+1)⁴,(i+1)³,(i+1)²,(i+1)¹,(i+1)⁰}.矩阵如下

　　　　0 2 0 0 0 0 0

　　　　1 1 0 0 0 0 0

　　　　0 1 1 0 0 0 0

　　　　0 4 4 1 0 0 0

　　　　0 6 6 3 1 0 0

　　　　0 4 4 3 2 1 0

　　　　0 1 1 1 1 1 1

　　推出转移矩阵后只需要根据n求矩阵快速幂即可。

  1 //
  2 //by coolxxx
  3 //#include<bits/stdc++.h>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<string>
  7 #include<iomanip>
  8 #include<map>
  9 #include<stack>
 10 #include<queue>
 11 #include<set>
 12 #include<bitset>
 13 #include<memory.h>
 14 #include<time.h>
 15 #include<stdio.h>
 16 #include<stdlib.h>
 17 #include<string.h>
 18 //#include<stdbool.h>
 19 #include<math.h>
 20 #pragma comment(linker,"/STACK:1024000000,1024000000")
 21 #define min(a,b) ((a)<(b)?(a):(b))
 22 #define max(a,b) ((a)>(b)?(a):(b))
 23 #define abs(a) ((a)>0?(a):(-(a)))
 24 #define lowbit(a) (a&(-a))
 25 #define sqr(a) ((a)*(a))
 26 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
 27 #define mem(a,b) memset(a,b,sizeof(a))
 28 #define eps (1e-8)
 29 #define J 10000
 30 #define mod 2147493647
 31 #define MAX 0x7f7f7f7f
 32 #define PI 3.14159265358979323
 33 #define N 14
 34 #define M 7
 35 using namespace std;
 36 typedef long long LL;
 37 double anss;
 38 LL aans;
 39 int cas,cass;
 40 int n,m,lll,ans;
 41 LL f[N];
 42 LL a[N][N];
 43 LL ma[N][N]={{0},
 44     {0,0,2,0,0,0,0,0},
 45     {0,1,1,0,0,0,0,0},
 46     {0,0,1,1,0,0,0,0},
 47     {0,0,4,4,1,0,0,0},
 48     {0,0,6,6,3,1,0,0},
 49     {0,0,4,4,3,2,1,0},
 50     {0,0,1,1,1,1,1,1}};
 51 void multi(LL a[][N],LL b[][N],LL c[][N])
 52 {
 53     int i,j,k;
 54     LL t[N][N];
 55     mem(t,0);
 56     for(i=1;i<=M;i++)
 57         for(j=1;j<=M;j++)
 58             for(k=1;k<=M;k++)
 59                 t[i][j]=(t[i][j]+a[i][k]*b[k][j]%mod)%mod;
 60     memcpy(c,t,sizeof(t));
 61 }
 62 void mi(LL a[][N],int y)
 63 {
 64     LL tmp[N][N];
 65     mem(tmp,0);
 66     tmp[1][1]=tmp[2][2]=tmp[3][3]=tmp[4][4]=tmp[5][5]=tmp[6][6]=tmp[7][7]=1;
 67     while(y)
 68     {
 69         if(y&1)multi(tmp,a,tmp);
 70         y>>=1;multi(a,a,a);
 71     }
 72     memcpy(a,tmp,sizeof(tmp));
 73 }
 74 void work()
 75 {
 76     LL t[N];
 77     mem(t,0);
 78     int i,j;
 79     for(i=1;i<=M;i++)
 80         for(j=1;j<=M;j++)
 81             t[i]=(t[i]+f[j]*a[j][i]%mod)%mod;
 82     memcpy(f,t,sizeof(t));
 83 }
 84 int main()
 85 {
 86     #ifndef ONLINE_JUDGE
 87     freopen("1.txt","r",stdin);
 88 //    freopen("2.txt","w",stdout);
 89     #endif
 90     int i,j,k;
 91     int x,y,z;
 92 //    init();
 93     for(scanf("%d",&cass);cass;cass--)
 94 //    for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
 95 //    while(~scanf("%s",s))
 96 //    while(~scanf("%d%d",&n,&m))
 97     {
 98         memcpy(a,ma,sizeof(a));
 99         scanf("%d%lld%lld",&n,&f[1],&f[2]);
100         f[3]=16,f[4]=8,f[5]=4,f[6]=2,f[7]=1;
101         if(n==1)
102         {
103             printf("%lld
",f[1]);
104             continue;
105         }
106         mi(a,n-2);
107         work();
108         printf("%lld
",f[2]);
109     }
110     return 0;
111 }
112 /*
113 //
114 
115 //
116 */

View Code