问题 D: 【例题4】佳佳的Fibonacci

问题 D: 【例题4】佳佳的Fibonacci

时间限制: 1 Sec  内存限制: 128 MB
提交: 5  解决: 4
[提交][状态][讨论版][命题人:quanxing][Edit] [TestData]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1704&pid=3

题目描述

佳佳对数学，尤其数列十分感兴趣，在研究Fibonacci之后，他创造出许多稀奇古怪的数列。如求S(n)表示Fibonacci数列前n项和对m取模之后的值，即S(n)=(F1+F2+...+Fn)mod m，F1=F2=1。可是这对佳佳来说还是小菜一碟。终于，他找到一个自己解决不了的数列。T(n)表示Fibonacci数列前n项变形后的和对m取模之后的值，

即T(n)=(F1+2×F2+3×F3+...+n*Fn)mod m，F1=F2=1。

输入

第一行，包含两个整数n和m。1<=n,m<=2的31次方-1

输出

共一行，T(n)的值

样例输入

5 5

样例输出

1

思路：

矩阵快速幂，加推导斐波那契数列的矩阵递推式，另外，我们知道菲波那切数列的前n项和等于菲波那切数列的第n-2项值-1

即：S(n)=F(n+2)-1

但这题没有单纯那么简单，因为这是一个带乘法系数的求和式子。

利用这个等式就可以快速算出

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll mod = 1e9 + 7;

ll n = 2, k;

struct MUL

{

    ll m[105][105];

}res;

MUL mul(MUL a, MUL b)//矩阵乘法，定义结构体函数，传入结构体，返回结构体，这样比较方便

{

    MUL tmp;

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

    {

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

         {

             tmp.m[i][j] = 0;

         }

    }

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

    {

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

         {

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

             {

                  tmp.m[i][j] = (tmp.m[i][j] % mod + (a.m[i][k] % mod * b.m[k][j] % mod) % mod) % mod;

             }

         }

    }

    return tmp;

}

MUL quickpow(MUL a, ll b, ll modd)//矩阵快速幂

{

    if (b == 1)return a;

    else

    {

         if (b % 2 == 0)

         {

             return quickpow(mul(a, a), b / 2, modd);

         }

         else

         {

             return mul(quickpow(mul(a, a), b / 2, modd), a);

         }

    }

}

int main()

{

    MUL A;

    cin >> k >> mod;

    A.m[1][1] = 1, A.m[1][2] = 1, A.m[2][1] = 1, A.m[2][2] = 0;//A是常数矩阵

    //Tn=n*F(n+2)-F(n+3)+2

    MUL result1 = quickpow(A, k + 2, mod);

    MUL result2 = quickpow(A, k + 3, mod);

    cout << (k*result1.m[1][2] - result2.m[1][2] + 2 + mod) % mod;

}