Another kind of Fibonacci
题目描述
As we all known , the Fibonacci series : (F)((0))(=1),(F)((1))(=1),(F)((N))(=F)((N-1))(+F)((N-2))((N ge 2)).Now we define another kind of Fibonacci : (A)((0))(=1),(A)((1))(=1),(A)((N))(=X *A)((N-1))(+Y*A)((N-2))((N ge 2)).And we want to Calculate (S)((N)),(S)((N))(=A)((0))(^2+A)((1))(^2+)……(+A)((n))(^2).
输入格式
There are several test cases.
Each test case will contain three integers,(N),(X),(Y).
(N):(2 le N le 2^{31}-1)
(X):(2 le X le 2^{31}-1)
(Y):(2 le Y le 2^{31}-1)
输出格式
For each test case , output the answer of (S)((n)).If the answer is too big , divide it by (10007) and give me the reminder.
样例输入
2 1 1 3 2 3
样例输出
6 196
题解
这道题如果只是求(f)((n))的话就和板题一样简单了，但是他要求的是(f(n))的平方的前缀和。
那么我们接下来开始构造矩阵：
首先很容易想到(S)((n))(=S)((n-1))+(f)((n))(^2)
那么我们的矩阵里现在有(S)((n))，(f)((n))(^2)两个元素。
但是我们无法转移(f)((n))(^2)，
所以我们把(f)((n))(^2)拆开来，
(f)((n))(^2=x^2*f)((n-1))(^2+2*x*y*f)((n-1))(*f)((n-2))(+y^2*f)((n-2))(^2)
我们又考虑到(f)((n))(*f)((n-1))(=)((x*f)((n-1))(+y*f)((n-2)))(*f)((n-1))(=x*f)((n-1))(^2+y*f)((n-1))(*f)((n-2))
那么我们再往矩阵里加上(f)((n-1))(^2)，(f)((n-1))(*f)((n-2))，就能完成转移了。
构造完后矩阵如下：
上面写的(f)((n))就是题目中的(A)((n))，习惯性地写成了(f)((n))，写完后也懒得改了，大家能理解就好了。
上代码：
#include<bits/stdc++.h>
#define mod 10007
using namespace std;
int n,x,y;
struct aa{
int a[9][9];
};
aa u;
aa cc(aa x,aa y){
aa ans;
for(int j=1;j<=4;j++)
for(int i=1;i<=4;i++){
ans.a[j][i]=0;
for(int o=1;o<=4;o++)
ans.a[j][i]=(ans.a[j][i]+x.a[j][o]*y.a[o][i])%mod;
}
return ans;
}
aa ksm(aa x,int p){
aa ans;
for(int j=1;j<=4;j++)
for(int i=1;i<=4;i++)
ans.a[j][i]=(j==i);
while(p){
if(p&1) ans=cc(ans,x);
x=cc(x,x);
p>>=1;
}
return ans;
}
int main(){
u.a[1][1]=u.a[3][2]=1;
while(scanf("%d%d%d",&n,&x,&y)!=EOF){
if(n==0){puts("1");continue;}
if(n==1){puts("2");continue;}
x%=mod;y%=mod;
u.a[1][2]=(x*x)%mod;
u.a[1][3]=(y*y)%mod;
u.a[1][4]=(2*x*y)%mod;
u.a[2][2]=(x*x)%mod;
u.a[2][3]=(y*y)%mod;
u.a[2][4]=(2*x*y)%mod;
u.a[4][2]=x;
u.a[4][4]=y;
aa ans=ksm(u,n-1);
int anss=0;
for(int j=2;j<=4;j++)
anss=(anss+ans.a[1][j])%mod;
printf("%d
",(anss+ans.a[1][1]*2)%mod);
}
return 0;
}