小奇的集合-白红宇

小奇的集合

阅读量：5069 次

发布时间：2019-06-12

本文共 1765 字，大约阅读时间需要 5 分钟。

要分最大值和次大值正负的四种情况...

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define rint register intusing namespace std;inline void read(int &x){ x=0; int ff=1; char q=getchar(); while(q<'0'||q>'9') { if(q=='-') ff=-1; q=getchar(); } while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar(); x*=ff;}inline void readll(ll &x){ x=0; int ff=1; char q=getchar(); while(q<'0'||q>'9') { if(q=='-') ff=-1; q=getchar(); } while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar(); x*=ff;}const int N=100005;const int mod=10000007;struct son{ ll b[7][7]; son(){mem(b,0);} son operator * (const son &c) const { int i,j,k; son x=*this,t; for(i=1;i<=3;++i) for(j=1;j<=3;++j) for(k=1;k<=3;++k) t.b[i][j]=(t.b[i][j]+x.b[i][k]*c.b[k][j]%mod)%mod; return t; } void out() { for(int i=1;i<=3;++i) { for(int j=1;j<=3;++j) printf("%lld ",b[i][j]); printf("\n"); } printf("\n"); }}f,a1,a2,a;int n;ll K;ll v[N];ll work(){ rint i,j,k; ll an=0; sort(v+1,v+1+n); for(i=1;i<=n;++i) an=(an+v[i])%mod; if(K==0) return (an+mod)%mod; if(v[n]<0) return (an+(v[n-1]+v[n]+mod+mod)%mod+mod)%mod; f.b[1][1]=v[n-1]; f.b[1][2]=v[n]; if(v[n-1]<0) { f.b[1][1]=v[n]+v[n-1]; an=(an+f.b[1][1])%mod; --K; } a1.b[1][2]=1; a1.b[2][1]=1; a1.b[2][2]=1; a1.b[3][3]=1; a2.b[2][3]=1; for(i=1;i<=3;++i) a2.b[i][i]=1; a=a1*a2; //a.out(); while(K) { if(K&1) f=f*a; a=a*a; //f.out(); K>>=1; } //printf("ff %lld\n",f.b[1][3]); an+=f.b[1][3]; while(an<=0) an+=mod; return an%mod;}int main(){ //freopen("in.in","r",stdin); rint i; read(n); readll(K); for(i=1;i<=n;++i) readll(v[i]); cout<