返回首页 返回专题

【BZOJ4547】小奇的集合 题解

考虑最大的两个数全为非负数的情况

显然每次找最大的两个数相加。设当前最大的数为F[2]，次大的数为F[1]，那么第一次操作F[3]=F[2]+F[1]，第二次操作F[4]=F[3]+F[2]，发现就是一个类斐波那契数列。我们可以用矩阵乘法求出其第n项及其前缀和。递推矩阵构造如下：

矩阵快速幂求出k次方即可

现在考虑最大的两个数都是负数的情况

显然每次都拿最大的两个数相加。把它们加起来乘k即可

现在考虑一正一负的情况

我们每次把那个正数与最大的负数相加，加起来会得到一个更大的负数，然后再把正数与得到的负数相加……如此循环，直到加出正数为止。因为数的绝对值不超过10^5，故上述操作至多进行10^5次，没有问题

最终时间复杂度O(ai + 9 log k)，快到飞起，B站2s的总时限都绰绰有余

#include<bits/stdc++.h>
#define Mod 10000007
using namespace std;
 
struct Matrix
{
    int m,n;
    int a[110][110];
} A,B;
 
Matrix operator * (const Matrix &a,const Matrix &b)
{
    Matrix c;
    c.m=a.m;c.n=b.n;
    for(int i=1;i<=a.m;i++)
        for(int j=1;j<=b.n;j++)
        {
            c.a[i][j]=0;
            for(int k=1;k<=a.n;k++)
                c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j]%Mod)%Mod;
        }
    return c;
}
 
Matrix operator ^ (Matrix a,int b)
{
    Matrix ans=a;b--;
    while(b)
    {
        if(b&1) ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
 
int main()
{
    int n,k,x,ans1=0,a1,a2;
    scanf("%d%d",&n,&k);
    scanf("%d%d",&a1,&a2);
    if(a1<a2) swap(a1,a2);
    for(int i=3;i<=n;i++)
    {
        scanf("%d",&x);
        if(x>a1) ans1=(ans1+a2)%Mod,a2=a1,a1=x;
        else if(x>a2) ans1=(ans1+a2)%Mod,a2=x;
        else ans1=(ans1+x)%Mod;
    }
    ans1=(ans1+a1+a2)%Mod;
    if(a1<=0&&a2<=0)
    {
        ans1=(ans1+1ll*k*(a1+a2)%Mod)%Mod;
        cout<<ans1<<endl;
        return 0;
    }
    while(a2<=0&&k>0) a2=a1+a2,ans1=(ans1+a2)%Mod,k--;
    if(k==0){cout<<ans1<<endl;return 0;}
    B.m=3;B.n=1;
    B.a[2][1]=a1;B.a[3][1]=a2;
    A.m=A.n=3;
    A.a[1][1]=A.a[1][2]=A.a[1][3]=1;
    A.a[2][2]=A.a[2][3]=A.a[3][2]=1;
    B=(A^k)*B;
    cout<<((ans1+B.a[1][1])%Mod+Mod)%Mod<<endl;
    return 0;
}