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

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了（毒瘤！！！）

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define mod 10000007
 7 using namespace std;
 8 typedef long long LL;
 9 struct node
10 {
11     LL m[5][5];
12     node(){memset(m,0,sizeof(m));}
13 }A,B,C,pre;
14 LL n,k,tt,max1,max2;
15 LL a[110000];
16 node multi(node a,node b)
17 {
18     node c;
19     for(int i=1;i<=3;i++)
20         for(int j=1;j<=3;j++)
21             for(int k=1;k<=3;k++)
22                 c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod;
23     return c;    
24 }
25 node sol(LL b)
26 {
27     node ans;
28     for(int i=1;i<=3;i++)ans.m[i][i]=1;
29     while(b)
30     {
31         if(b%2==1)ans=multi(ans,pre);
32         pre=multi(pre,pre);b/=2;
33     }
34     return ans;
35 }
36 int main()
37 {
38     freopen("4547.in","r",stdin);
39     freopen("ans.out","w",stdout);
40     scanf("%lld%lld",&n,&k);LL sum=0;
41     for(int i=1;i<=n;i++)scanf("%lld",&a[i]),sum=(sum+a[i]+mod)%mod;
42     sort(a+1,a+n+1);max1=a[n];max2=a[n-1];
43     if(max2<0 && max1>0)
44     {
45         tt=0;
46         while(max2<0)
47         {
48             max2+=max1;
49             sum=(sum+max2+mod)%mod;
50             tt++;
51         }
52         if(max2>max1)swap(max2,max1);
53     }
54     pre.m[1][1]=pre.m[1][2]=pre.m[1][3]=pre.m[2][2]=pre.m[2][3]=pre.m[3][2]=1;
55     A=sol(k-tt);
56     B.m[1][1]=sum,B.m[2][1]=max1,B.m[3][1]=max2;
57     C=multi(A,B);
58     printf("%lld
",C.m[1][1]%mod);
59     return 0;
60 }