欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[hdu517] 小奇的集合

程序员文章站 2022-04-29 18:08:00
"题目链接" 显然有贪心每次选择最大的两个数来做。 于是暴力地把最大的两个数调整到非负(暴力次数不超过1e5),接下来使用矩阵乘法即可。 $$ \begin{pmatrix} B'\\S'\\T' \end{pmatrix} = \begin{pmatrix} 1&1&0\\ 1&0&0\\ 1&1 ......

题目链接

显然有贪心每次选择最大的两个数来做。

于是暴力地把最大的两个数调整到非负(暴力次数不超过1e5),接下来使用矩阵乘法即可。

\[ \begin{pmatrix} b'\\s'\\t' \end{pmatrix} = \begin{pmatrix} 1&1&0\\ 1&0&0\\ 1&1&1 \end{pmatrix} \begin{pmatrix} b\\s\\t \end{pmatrix} \]

#include <bits/stdc++.h>
using namespace std;
const int mod=1e7+7;

struct node {
    int a[3][3];
    int *operator[](const int&d) {return a[d];}
    const int *operator[](const int&d) const{return a[d];}
    node operator*(const node&b) const{
        node c; 
        memset(&c,0,sizeof c);
        for(int i=0; i<3; ++i) 
        for(int k=0; k<3; ++k) if(a[i][k])
        for(int j=0; j<3; ++j)
            c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j]%mod)%mod;
        return c;
    }
    node pow(int y) {
        node c,x=*this;
        for(int i=0; i<3; ++i) 
        for(int j=0; j<3; ++j) c[i][j]=(i==j);
        for(; y; y>>=1,x=x*x) if(y&1) c=c*x;
        return c;
    }
} g,m;

int n,k,sum,a[200010];

int main() {
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; ++i) {
        scanf("%d",a+i);
        sum=(sum+a[i]+mod)%mod;
    }
    sort(a+1,a+n+1);
    while(a[n-1]<0&&k>0) {
        a[n+1]=(a[n]+a[n-1]); n++; k--;
        sum=(sum+a[n]+mod)%mod;
        swap(a[n],a[n-1]);
    }
    if(k==0) {
        printf("%d\n",sum);
        return 0;
    }
    m[0][0]=a[n];
    m[1][0]=a[n-1];
    m[2][0]=sum;
    g[0][0]=g[0][1]=1;
    g[1][0]=1;
    g[2][0]=g[2][1]=g[2][2]=1;
    node ans=g.pow(k)*m;
    printf("%d\n",ans[2][0]);
    return 0;
}