程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu5171---GTY&#39;s birthday gift

hdu5171---GTY&#39;s birthday gift

編輯：C++入門知識

hdu5171---GTY's birthday gift

Problem Description
FFZ’s birthday is coming. GTY wants to give a gift to ZZF. He asked his gay friends what he should give to ZZF. One of them said, ‘Nothing is more interesting than a number multiset.’ So GTY decided to make a multiset for ZZF. Multiset can contain elements with same values. Because GTY wants to finish the gift as soon as possible, he will use JURUO magic. It allows him to choose two numbers a and b(a,b∈S), and add a+b to the multiset. GTY can use the magic for k times, and he wants the sum of the multiset is maximum, because the larger the sum is, the happier FFZ will be. You need to help him calculate the maximum sum of the multiset.

Input
Multi test cases (about 3) . The first line contains two integers n and k (2≤n≤100000,1≤k≤1000000000). The second line contains n elements ai (1≤ai≤100000)separated by spaces , indicating the multiset S .

Output
For each case , print the maximum sum of the multiset (mod 10000007).

Sample Input

3 2 3 6 2

Sample Output

Source
BestCoder Round #29

Recommend
hujie | We have carefully selected several similar problems for you: 5173 5172 5169 5168 5165

設現在拿出的數為a和b，且a >= b,則下一次拿出的數為 a + b， a
存在遞推關系，得到遞推矩陣後，快速冪求解即可，復雜度O（logn）

/*************************************************************************
    > File Name: hdu5171.cpp
    > Author: ALex
    > Mail: [email protected] 
    > Created Time: 2015年02月14日 星期六 10時48分07秒
 ************************************************************************/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair  PLL;
const int mod = 10000007;

struct MARTIX
{
    LL mat[3][3];
};

MARTIX mutiple (MARTIX A, MARTIX B)
{
    MARTIX C;
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            C.mat[i][j] = 0;
            for (int k = 0; k < 3; ++k)
            {
                C.mat[i][j] += A.mat[i][k] * B.mat[k][j];
                C.mat[i][j] %= mod;
            }
        }
    }
    return C;
}

void POW (LL a, LL b, LL s, int k)
{
    MARTIX ret, ans, bse;
    ret.mat[0][0] = ret.mat[0][1] = ret.mat[0][2] = 1;
    ret.mat[1][0] = ret.mat[2][0] = ret.mat[2][2] = 0;
    ret.mat[1][1] = ret.mat[1][2] = ret.mat[2][1] = 1;
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            ans.mat[i][j] = (i == j ? 1 : 0);
            bse.mat[i][j] = 0;
        }
    }
    bse.mat[0][0] = s;
    bse.mat[1][0] = a;
    bse.mat[2][0] = b;
    while (k)
    {
        if (k & 1)
        {
            ans = mutiple (ans, ret);
        }
        k >>= 1;
        ret = mutiple (ret, ret);
    }
    ans = mutiple (ans, bse);
    printf("%lld\n", ans.mat[0][0]);
}

int main ()
{
    int n, k;
    while (~scanf("%d%d", &n, &k))
    {
        LL m1 = -inf, m2 = -inf;
        LL s = 0;
        LL t;
        for (int i = 1; i <= n; ++i)
        {
            scanf("%lld", &t);
            s += t;
            if (m1 < t)
            {
                m2 = m1;
                m1 = t;
            }
            else if (m2 < t)
            {
                m2 = t;
            }
        }
        POW (m1, m2, s, k);
    }
    return 0;
}