【BZOJ-4547】小奇的集合 矩阵乘法 + 递推

时间：2021-09-30 09:05:36

4547: Hdu5171 小奇的集合

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 175  Solved: 85
[Submit][Status][Discuss]

Description

有一个大小为n的可重集S，小奇每次操作可以加入一个数a+b(a,b均属于S)，求k次操作后它可获得的S的和的最大

值。（数据保证这个值为非负数）

Input

第一行有两个整数n,k表示初始元素数量和操作数，第二行包含n个整数表示初始时可重集的元素。

对于100%的数据，有 n<=10^5，k<=10^9，|ai|<=10^5

Output

输出一个整数，表示和的最大值。答案对10000007取模。

Sample Input

2 2
3 6

Sample Output

33

HINT

Source

By Hzwer

Solution

很显然，每次操作都是取最大和次大相加，然后如此下去

如此这样发现，显然是一个fib前缀和的问题，那么显然可以递推

优化这个递推，显然可以矩阵乘法

$\begin{bmatrix}S[max]&  S[cmax]& Sum \end{bmatrix}*(\begin{bmatrix} 1& &1& &0\\ 1& &0& &0\\ 1& &1& &1 \end{bmatrix})^{K}$

其中S[max]表示最大，S[cmax]表示次大

如果初始的次大<0先不断累加最大，到>=0为止，然后进行上述处理

Code

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int  read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define MAXN 100010

#define L 4

#define sz 3

#define p 10000007

int N,K;

int S[MAXN];

int sum;

struct MatNode{int a[L][L]; MatNode() {memset(a,,sizeof(a));}}A,D;

MatNode MatMul(MatNode X,MatNode Y)

{

    MatNode C;

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

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

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

                if (X.a[i][k] && Y.a[k][j])

                    (C.a[i][j]+=(long long)X.a[i][k]*Y.a[k][j]%p)%=p;

    return C;

}

MatNode MatPow(MatNode x,int y)

{

    MatNode re;

    for (int i=; i<=sz; i++) re.a[i][i]=;

    for (int i=y; i; i>>=,x=MatMul(x,x))

        if (i&) re=MatMul(re,x);

    return re;

}

void BuildMat()

{

    A.a[][]=; A.a[][]=; A.a[][]=;

    A.a[][]=; A.a[][]=; A.a[][]=;

    A.a[][]=; A.a[][]=; A.a[][]=;

    D.a[][]=S[]; D.a[][]=S[]; D.a[][]=sum;

}

bool cmp(int a,int b) {return a>b;}

int main()

{

    N=read(),K=read();

    for (int i=; i<=N; i++) S[i]=read(),sum+=S[i],sum=(sum+p)%p;

    sort(S+,S+N+,cmp);

    while (S[]< && K>)

        {

            S[]=(S[]+S[])%p; K--;

            sum+=S[]; sum=(sum+p)%p;

        }

    BuildMat();

    D=MatMul(MatPow(A,K),D);

    int ans=(D.a[][]+p)%p;

    printf("%d\n",ans);

    return ;

}

相关文章