hdu5171（矩阵快速幂）

传送门：GTY's birthday gift

题意：GTY的朋友ZZF的生日要来了，GTY问他的基友送什么礼物比较好，他的一个基友说送一个可重集吧！于是GTY找到了一个可重集S，GTY能使用神犇魔法k次，每次可以向可重集中加入一个数 a+b(a,b∈S)，现在GTY想最大化可重集的和，这个工作就交给你了。注：可重集是指可以包含多个相同元素的集合

分析：想要和最大，那么每次必定从集合里面拿出最大的两个出来相加，然后k次后面就类似斐波那契数列了。

由斐波那契数列公式知：F_n=F_n-1+F_n-2，求和公式有S_n=S_n-1+F_n.因此用这两个公式构造矩阵，进行矩阵快速幂。

S_n-1 | 1 1 0| S_n

F_n * | 0 1 1| =F_n+1

F_n-1 | 0 1 0| F_n

然后ans=(S_n+（sum-a[n-1]-a[n-2]）)%mod(sum为原集合总和，然后减去最大的两个，加上k次后的序列之和（即斐波那契数列和）)。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstdlib>

#include <stack>

#include <vector>

#include <set>

#include <map>

#define LL long long

#define mod 10000007

#define inf 0x3f3f3f3f

#define N 40010

#define clr(a) (memset(a,0,sizeof(a)))

using namespace std;

struct matrix

{

    LL m[][];

};

LL a[];

matrix mult(matrix a,matrix b)

{

    matrix c;

    memset(c.m,,sizeof(c.m));

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

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

    {

        if(a.m[i][j]==)continue;

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

        {

            if(b.m[j][k]==)continue;

            c.m[i][k]+=a.m[i][j]*b.m[j][k]%mod;

            c.m[i][k]%=mod;

        }

    }

    return c;

}

matrix quickmod(matrix a,int n)

{

    matrix temp;

    memset(temp.m,,sizeof(temp.m));

    for(int i=;i<=;i++)temp.m[i][i]=;

    while(n)

    {

        if(n&)temp=mult(temp,a);

        a=mult(a,a);

        n/=;

    }

    return temp;

}

int main()

{

    LL n,k;

    while(scanf("%I64d%I64d",&n,&k)>)

    {

        LL sum=;

        for(int i=;i<n;i++)scanf("%I64d",&a[i]),sum+=a[i];

        sort(a,a+n);

        matrix ans;

        ans.m[][]=;ans.m[][]=;ans.m[][]=;

        ans.m[][]=;ans.m[][]=;ans.m[][]=;

        ans.m[][]=;ans.m[][]=;ans.m[][]=;

        ans=quickmod(ans,k+);

        printf("%I64d\n",(1LL*ans.m[][]*a[n-]+1LL*ans.m[][]*a[n-]+1LL*ans.m[][]*a[n-]+sum-(a[n-]+a[n-]))%mod);

    }

}

巴特西

hdu5171（矩阵快速幂）

最新文章

热门文章