SPOJ:Fibonacci Polynomial(矩阵递推&前缀和)

Problem description.

The Fibonacci numbers defined as f(n) = f(n-1) + f(n-2) where f0 = 0 and f1 = 1.

We define a function as follows D(n,x) = x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 +...+f(n)x^n

Given two integers n and x, you need to compute D(n,x) since the output can be very large output the result modulo 1000000007 (1e9+7) .

Input

Input description.

The first line of the input contains an integer T denoting the number of test cases.
The description of T test cases follows.
The first line of each test case contains two integers n and x as described above.

Output

Output description.

For each test case, output D(n,x)%1000000007 in a seperate line.

Constraints

Should contain all the constraints on the input data that you may have. Format it like:

1 ≤ T ≤ 1000
0 ≤ n ≤ 10^15
0 ≤ x ≤ 10^15

Example

Input:

1

7 11

Output:

268357683

题意：f(n)是斐波拉契数列，g(n)=f(n)*x^n；求前N项的g(n)的累加和。

思路：易得g(n)=g(n-1)*x+g(n-2)*x^2，

可以得到g(n)的矩阵求解方程： g(n)=base^N*g(0); 其中，base[1][1]=X; base[1][2]=X^2; base[2][1]=1（由递推式得到）;

前缀和可以由大矩阵得到：A[1][1]=base; A[1][2]=1; A[2][2]=1（有前缀和求和公式得到）；

大概地解释了一下，不是很清楚，可以看代码。前缀和可以参考这里：http://www.cnblogs.com/hua-dong/p/8479103.html

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

const int Mod=1e9+;struct mat

{

    ll mp[][];

    mat(){memset(mp,,sizeof(mp)); }

    mat friend operator *(mat a,mat b)

    {

        mat res;

        for(int k=;k<=;k++)

         for(int i=;i<=;i++)

          for(int j=;j<=;j++)

            res.mp[i][j]=(res.mp[i][j]+(a.mp[i][k]*b.mp[k][j])%Mod)%Mod;

        return res;

    }

    mat friend operator ^(mat a,ll x)

    {

        mat res;

        for(int i=;i<=;i++) res.mp[i][i]=;

        while(x){

            if(x&) res=res*a;  a=a*a;  x>>=;

        }   return res;

    }

};

int main()

{

    ll T,N,X;

    scanf("%lld",&T);

    while(T--){

        scanf("%lld%lld",&N,&X); X%=Mod;

        mat base;

        base.mp[][]=X; base.mp[][]=X*X%Mod; base.mp[][]=;

        for(int i=;i<=;i++) base.mp[i][i+]=base.mp[i+][i+]=;

        base=base^N;

        printf("%lld\n",base.mp[][]*X%Mod);

    }

    return ;

}

巴特西

SPOJ:Fibonacci Polynomial(矩阵递推&前缀和)

Input

Output

Constraints

Example

最新文章

热门文章