4547: Hdu5171 小奇的集合

题目：传送门

题解：

　　做一波大佬们的坑...ORZ

　　不得不说，我觉得矩阵很简单啊，就一个3*3的（直接看代码吧）

　　给个递推柿纸：f[i]=f[i-1]+max1+max2

　　因为题目保证答案非负，那么一般情况下，肯定是将max1+max2加入原数列啊

　　兴高采烈的一顿乱水，nice！一WA

　　 md被CC无情嘲笑...

　　再看一波题目...abs(a[i])<=10^5???

　　有负数？！

　　 woc那如果max2<0那么我不就GG？？？

　　好的又是一顿乱水，直接暴力将max2变为正数...

　　 nice！二WA！

　　对拍！mmp。。。

　　一千年过去了..."仍无差异"

　　 %一发企鹅，发现他的sum加的时候先加了一个mod！？

　　 woc求和时加过了mod之后来个很小的负数我又挂了...然后小心翼翼的改了再提交

　　终于...A了（毒瘤！！！）

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #define mod 10000007

 using namespace std;

 typedef long long LL;

 struct node

 {

     LL m[][];

     node(){memset(m,,sizeof(m));}

 }A,B,C,pre;

 LL n,k,tt,max1,max2;

 LL a[];

 node multi(node a,node b)

 {

     node c;

     for(int i=;i<=;i++)

         for(int j=;j<=;j++)

             for(int k=;k<=;k++)

                 c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod;

     return c;

 }

 node sol(LL b)

 {

     node ans;

     for(int i=;i<=;i++)ans.m[i][i]=;

     while(b)

     {

         if(b%==)ans=multi(ans,pre);

         pre=multi(pre,pre);b/=;

     }

     return ans;

 }

 int main()

 {

     freopen("4547.in","r",stdin);

     freopen("ans.out","w",stdout);

     scanf("%lld%lld",&n,&k);LL sum=;

     for(int i=;i<=n;i++)scanf("%lld",&a[i]),sum=(sum+a[i]+mod)%mod;

     sort(a+,a+n+);max1=a[n];max2=a[n-];

     if(max2< && max1>)

     {

         tt=;

         while(max2<)

         {

             max2+=max1;

             sum=(sum+max2+mod)%mod;

             tt++;

         }

         if(max2>max1)swap(max2,max1);

     }

     pre.m[][]=pre.m[][]=pre.m[][]=pre.m[][]=pre.m[][]=pre.m[][]=;

     A=sol(k-tt);

     B.m[][]=sum,B.m[][]=max1,B.m[][]=max2;

     C=multi(A,B);

     printf("%lld\n",C.m[][]%mod);

     return ;

 }

巴特西

bzoj4547: Hdu5171 小奇的集合(矩阵乘法)

4547: Hdu5171 小奇的集合

最新文章

热门文章