BZOJ 4547 矩阵快速幂

2019-11-06 07:30:02

字体：大中小

来源：转载

供稿：网友

思路：肯定每回只加最大值和次大值

如果一开始的最大值>0且次大值<0 那就一直加加到次大值>0

搞一个矩阵推斐波那契数列求和就好…

//By SiriusRen#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int mod=10000007,N=100050;#define int long longint n,k,ans,maxx1=-mod,maxx2=-mod,a[N];struct Matrix{ int a[4][4]; void init(){memset(a,0,sizeof(a));} void bgn(){a[1][1]=a[3][1]=a[3][2]=a[3][3]=a[1][2]=a[2][1]=1;}}fst,change,jy;Matrix Operator*(Matrix a,Matrix b){ Matrix c;c.init(); for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) for(int k=1;k<=3;k++) (c.a[i][j]+=a.a[i][k]*b.a[k][j])%=mod; return c;}bool cmp(int a,int b){return a>b;}Matrix pow(Matrix a,int y){ Matrix res;res.init(); for(int i=1;i<=3;i++)res.a[i][i]=1; while(y){ if(y&1)res=res*a; a=a*a,y>>=1; }return res;}signed main(){ scanf("%lld%lld",&n,&k),change.bgn(); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]),ans=(ans+a[i])%mod; if(a[i]>maxx2&&a[i]<=maxx1)maxx2=a[i]; else if(a[i]>maxx2&&a[i]>maxx1)maxx2=maxx1,maxx1=a[i]; } while(maxx1>0&&maxx2<0&&k>0)maxx2+=maxx1,(ans+=maxx2)%=mod,k--; change.bgn(),fst.a[1][1]=maxx1,fst.a[2][1]=maxx2,fst.a[3][1]=ans; jy=pow(change,k)*fst; PRintf("%lld/n",(jy.a[3][1]+mod)%mod);}

这里写图片描述