HDU5171 矩阵快速幂

　　题目描述：http://acm.hdu.edu.cn/showproblem.php?pid=5171

算法：　　

　　可以先将数组a[]排序，然后序列 a₁ , a₂ , … , a_n 即为有序序列，则第一次加入的就是 a_n + a_n-1 ,第二次就是 a_n + (a_n + a_n-1) ,如此循环就构成了斐波那契序列。

　　设斐波那契序列的第k项为F_k，则可知第k次加入的即为 F_k+1*a_n + F_k * a_n-1

　　设斐波那契序列的前k项和为S_k，则所得结果res即为：a₁ + a₂ + … + a_n-1+a_n + (S_k+1 - 1) * a_n + S_k*a_n-1

实现方法：

　　由于需要对结果取余，所以可以考虑用矩阵快速幂来实现斐波那契序列，具体怎么实现可以看这里。

　　并且根据公式可以知道 S_k = 2 * F_k + F_k-1 - 1 , 代入上式即可。

#include <iostream>

#include <cstdio>

#include <vector>

#include <cmath>

#include <string>

#include <string.h>

#include <algorithm>

using namespace std;

#define LL __int64

#define eps 1e-8

const int MOD = ;

const int maxn =  + ;

const int N = ;

struct Mat {

    LL mat[N][N];

} a;

void init()

{

    a.mat[][] = a.mat[][] = a.mat[][] = ;

    a.mat[][] = ;

}

Mat operator *(Mat a , Mat b)

{

    Mat tmp;

    memset(tmp.mat ,  , sizeof(tmp.mat));

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

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

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

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

    return tmp;

}

Mat operator ^(Mat a , int k)

{

    Mat tmp;

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

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

            tmp.mat[i][j] = (i == j);

    while(k) {

        if(k & )

            tmp = tmp * a;

        a = a * a;

        k /= ;

    }

    return tmp;

}

LL Fib(int k)

{

    Mat tmp;

    tmp = a ^ k;

    return tmp.mat[][];

}

LL a_[maxn];

int main()

{

    init();

    LL n , k , i , j , res;

    while(~scanf("%lld %lld" , &n , &k))

    {

        for(i =  , res =  ; i <= n ; i++) {

            scanf("%lld" , &a_[i]);

            res += a_[i];

        }

        sort(a_ +  , a_ + n + );

        LL tmp = (( * Fib(k + ) + Fib(k) + ) * a_[n] + ( * Fib(k) + Fib(k - ) + ) * a_[n - ]) % MOD;

        res = (res + tmp) % MOD;

        printf("%lld\n" , res);

    }

    return ;

}

另外记录一个斐波那契的通项公式：，在HDU1568中会用这个公式。

巴特西

HDU5171 矩阵快速幂

最新文章

热门文章