BZOJ 4547 Hdu 5171小奇の集合【マトリックス高速べき乗最適化繰返し】

BZOJ 4547 Hdu 5171小奇の集合
Description
nの大きさの再セット可能なSがあり、小奇は操作ごとにa+b(a,bはいずれもSに属する)の数を加え、k回の操作後に得られるSの和の最大値を求めることができる.(データはこの値が非負であることを保証する)
Input
1行目には2つの整数nがあり、kは初期要素の数とオペランドを表し、2行目にはn個の整数が初期時に再セット可能な要素を含む.100%のデータに対してn<=105,k<=109,|ai|<=10^5
Output
和の最大値を表す整数を出力します.答えは1000007型を取ります.
Sample Input
2 2 3 6
Sample Output
33
まず,最大値と次大値が正数である場合,マトリクス高速べき乗で直接最適化すればよい場合,最大値が正数であり,次大値が負数である場合,まず次大値を正数に加算し,マトリクス高速べき乗を最大と次大部分が負数である場合,直接答えを算出できることを状況別に検討する.
その後、マトリクスの高速べき乗は一般的で、現在の最大値と二次大値とsumを記録して、マトリクスを移動して簡単に自分で押すといいです.

#include
using namespace std;
#define fu(a,b,c) for(int a=b;a<=c;++a)
#define N 100010
#define INF 0x3f3f3f3f
#define LL long long
#define Mod 10000007
struct Matrix{LL t[3][3];};
Matrix mul(Matrix a,Matrix b){
  Matrix c;
  memset(c.t,0,sizeof(c.t));
  fu(i,0,2)fu(j,0,2)fu(k,0,2)
    c.t[i][j]=(c.t[i][j]+a.t[i][k]*b.t[k][j]%Mod+Mod)%Mod;
  return c;
}
Matrix fast_pow(Matrix a,LL b){
  Matrix ans;
  fu(i,0,2)fu(j,0,2)ans.t[i][j]=(i==j);
  while(b){
    if(b&1)ans=mul(ans,a);
    a=mul(a,a);
    b>>=1;
  }
  return ans;
}
int solve(LL max1,LL max2,LL k){
  Matrix tmp,ans;
  tmp.t[0][0]=1;tmp.t[0][1]=1;tmp.t[0][2]=1;
  tmp.t[1][0]=1;tmp.t[1][1]=0;tmp.t[1][2]=1;
  tmp.t[2][0]=0;tmp.t[2][1]=0;tmp.t[2][2]=1;
  tmp=fast_pow(tmp,k);
  ans.t[0][0]=max1;ans.t[0][1]=max2;ans.t[0][2]=0;
  ans.t[1][0]=0;ans.t[1][1]=0;ans.t[1][2]=0;
  ans.t[2][0]=0;ans.t[2][1]=0;ans.t[2][2]=0;
  ans=mul(ans,tmp);
  return ans.t[0][2];
}
int main(){
  LL n,k,sum=0,max1=-INF,max2=-INF;
  scanf("%lld%lld",&n,&k);
  fu(i,1,n){
    LL x;scanf("%lld",&x);
    sum=(sum+x%Mod+Mod)%Mod;
    if(x>max1)max2=max1,max1=x;
    else if(x>max2)max2=x;
  }
  if(max1>0&&max2>0)printf("%lld",(sum+solve(max1,max2,k)+Mod)%Mod);
  else if(max1<0&&max2<0)printf("%lld",(sum+(max1+max2)*k%Mod+Mod)%Mod);
  else{
    int cnt=0;
    while(max2<0){
      int newv=max1+max2;
      if(newv>max1){max2=max1,max1=newv;}
      else{max2=newv;}
      sum=(sum+newv)%Mod;
      cnt++;
      if(cnt==k)break;
    }
    if(cnt==k)printf("%lld",(sum+Mod)%Mod);
    else printf("%lld",(sum+solve(max1,max2,k-cnt)+Mod)%Mod);
  }
  return 0;
}