问一个和斐波那契有关的题

#include <stdio.h>
#define M 108
int main(){
int N,X;
int i,a,b,x,ans;
scanf("%d%d",&N,&X);
a=b=1,x=X,ans=0;
for(i=0;i<N;i++){
ans=(ans+(a*x)%M)%M;
b=a+b, a=b-a;
b%=M, a%=M;
x=(x*X)%M;
}
printf("%d\n",ans);
return 0;
}

还没有回答的啊……我给贴个O(k*log(N))……k是常数（要超过50，比较大，所以写出来了）
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
/* 矩阵幂取模 模板*/
struct mat{
int at[3][3];
};
mat d;
int n,mod;
mat mul(mat a,mat b)
{
mat t;
memset(t.at,0,sizeof(t.at));
for(int i=0;i<n;++i)
{
for(int k=0;k<n;++k)
{
if(a.at[i][k])
for(int j=0;j<n;++j)
{
t.at[i][j]+=a.at[i][k]*b.at[k][j];
if(t.at[i][j]>=mod){t.at[i][j]%=mod;}
}
}
}
return t;
}
mat expo(mat p,int k)
{
if(k==1)return p;
mat e;
memset(e.at,0,sizeof(e.at));
for(int i=0;i<n;++i){e.at[i][i]=1;}
if(k==0)return e;
while(k)
{
if(k&1)e=mul(p,e);
p=mul(p,p);
k>>=1;
}
return e;
}
int main()
{
int N,X;
n=3;
mod=100000000;
scanf("%d%d",&N,&X);
int ans;
if(N==0){
ans=0;
} else if (N==1){
ans=X%mod;
} else {
d.at[0][0]=X;
d.at[0][1]=X*X;
d.at[1][0]=d.at[2][2]=d.at[0][2]=1;
d.at[1][1]=d.at[1][2]=d.at[2][0]=d.at[2][1]=0;
mat ret=expo(d,N-1);
ans=(((ret.at[0][0]%mod)*(X%mod)%mod)+((ret.at[0][2]%mod)*(X%mod))%mod)%mod;
}
printf("%d\n",ans);
return 0;
}

A(N,X)=F(1)*X+F(2)*X^2+F(3)*X^3+...+F(N)*X^N
使用斐波那契的递推公式，F(N)=F(N-1)+F(N-2)，则
==>A(N,X)=F(1)*X+[F(0)+F(1)]*X^2+[F(1)+F(2)]*X^3+...+[F(N-2)+F(N-1)]*X^N
==>A(N,X)=F(1)*X+　　　F(1)*X^2+　　　F(2)*X^3+...　　　　+F(N-1)*X^N
　　　　　　　　　+0　　　　　　+F(1)*X^3　　　+...+F(N-2)*X^N
==>A(N,X)=X+X*A(N-1,X)+X^2*A(N-2,X)
　　| A(N,X)　 |　　|　X　X^2　1　|　| A(N-1,X) |
==>| A(N-1,X) |　=　|　1　0　　0　|*　| A(N-2,X)|
　　|　X　　　|　　|　0　0　　1　|　|　X　　　|
　　| A(N,X)　|　　　|　X　X^2　1 |^(N-1)　| A(1,X) |
==>| A(N-1,X) |　=　　|　1　0　0 |　　　* | A(0,X) |
　　|　X　　　|　　　|　0 　0　1 |　　　　|　　X　|
　　| A(N,X)　|　　　| X　X^2　　1 |^(N-1)　　| X |
==>| A(N-1,X) |　=　　| 1 0　　0 |　　　 *　| 0 |
　　|　　X　　|　　　|　0　　0　1 |　　　　　| X |
然后直接是矩阵幂取模，自己找模板学吧。经典算法。