Recursive sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 249 Accepted Submission(s): 140Problem DescriptionFarmer 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 i4. Now, you need to write a program to calculate the number of the N-th cow in order to check if John’s cows can make it right.InputThe 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 < 231 as described above.OutputFor 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 Input2
3 1 2
4 1 10Sample Output85
369HintIn 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.SourceRecommendjiangzijing2015 | We have carefully selected several similar problems for you: 5960 5959 5958 5957 5956
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5950
题目大意：
Fi=Fi-1+2Fi-2+i4。给定F1和F2求Fn。
题目思路：
【递推+矩阵快速幂】
现场用算了1个多小时的公式过了。
主要还是我太菜。递推写的太少。
先考虑f(i)=f(i-1)+2f(i-2)，很容易写出递推矩阵
0 2
1 1
(i+1)4=i4+4i3+6i2+4i+1。
所以需要在递推矩阵种存下i的4 3 2 1 0次幂，以便推出(i+1)4，矩阵为
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={fi-1,fi,i4,i3,i2,i1,i0}，将以上两个矩阵合并，即可推出{fi,fi+1,(i+1)4,(i+1)3,(i+1)2,(i+1)1,(i+1)0}.矩阵如下
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求矩阵快速幂即可。
//
//by coolxxx
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<bitset>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#include<stdbool.h>
#include<math.h>
#pragma comment(linker,"/STACK:1024000000,1024000000")
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define eps (1e-8)
#define J 10000
#define mod 2147493647
#define MAX 0x7f7f7f7f
#define PI 3.14159265358979323
#define N 14
#define M 7
using namespace std;
typedef long long LL;
double anss;
LL aans;
int cas,cass;
int n,m,lll,ans;
LL f[N];
LL a[N][N];
LL ma[N][N]={{},
{,,,,,,,},
{,,,,,,,},
{,,,,,,,},
{,,,,,,,},
{,,,,,,,},
{,,,,,,,},
{,,,,,,,}};
void multi(LL a[][N],LL b[][N],LL c[][N])
{
int i,j,k;
LL t[N][N];
mem(t,);
for(i=;i<=M;i++)
for(j=;j<=M;j++)
for(k=;k<=M;k++)
t[i][j]=(t[i][j]+a[i][k]*b[k][j]%mod)%mod;
memcpy(c,t,sizeof(t));
}
void mi(LL a[][N],int y)
{
LL tmp[N][N];
mem(tmp,);
tmp[][]=tmp[][]=tmp[][]=tmp[][]=tmp[][]=tmp[][]=tmp[][]=;
while(y)
{
if(y&)multi(tmp,a,tmp);
y>>=;multi(a,a,a);
}
memcpy(a,tmp,sizeof(tmp));
}
void work()
{
LL t[N];
mem(t,);
int i,j;
for(i=;i<=M;i++)
for(j=;j<=M;j++)
t[i]=(t[i]+f[j]*a[j][i]%mod)%mod;
memcpy(f,t,sizeof(t));
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k;
int x,y,z;
// init();
for(scanf("%d",&cass);cass;cass--)
// for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
// while(~scanf("%s",s))
// while(~scanf("%d%d",&n,&m))
{
memcpy(a,ma,sizeof(a));
scanf("%d%lld%lld",&n,&f[],&f[]);
f[]=,f[]=,f[]=,f[]=,f[]=;
if(n==)
{
printf("%lld\n",f[]);
continue;
}
mi(a,n-);
work();
printf("%lld\n",f[]);
}
return ;
}
/*
// //
*/