hdu 5171 GTY's birthday gift（数学，矩阵快速幂）

题意：

开始时集合中有n个数。

现在要进行k次操作。

每次操作：从集合中挑最大的两个数a,b进行相加，得到的数添加进集合中。

以此反复k次。

问最后集合中所有数的和是多少。

(2≤n≤100000,1≤k≤1000000000)

思路：

写出来发现是要求Fibonaci的前n个数的和。

Fibonaci是用矩阵快速幂求的，这个也可以。

[Sn,Fn,Fn-1]=[某个矩阵]*[Sn-1,Fn-1,Fn-2]

[S2,F2,F1]=[2,1,1]

然后写，，，

这个代码有些繁琐，应该把矩阵操作单独写成函数。

日后更新。

代码：

ll const mol = 10000007;

int n,k;

ll ans;

ll matrix[4][4];

int a[100005];

void matrixSolve(int k){ // ¾ØÕóµÄk´Î·½

    if(k==0){

        mem(matrix,0);

        matrix[1][1]=1;

        matrix[2][2]=1;

        matrix[3][3]=1;

        return;

    }

    if(k==1){

        mem(matrix,0);

        matrix[1][1]=matrix[1][2]=matrix[1][3]=1;

        matrix[2][2]=matrix[2][3]=1;

        matrix[3][2]=1;

        return;

    }

    matrixSolve(k/2);

    ll tempMatrix[4][4];

    mem(tempMatrix,0);

    rep(i,1,3){

        rep(j,1,3){

            rep(k,1,3){

                tempMatrix[i][j]=(tempMatrix[i][j]+matrix[i][k]*matrix[k][j]%mol)%mol;

            }

        }

    }

    rep(i,1,3){

        rep(j,1,3){

            matrix[i][j]=tempMatrix[i][j];

        }

    }

    if((k&1)==1){

        ll temp2Matrix[4][4];

        mem(temp2Matrix,0);

        temp2Matrix[1][1]=temp2Matrix[1][2]=temp2Matrix[1][3]=1;

        temp2Matrix[2][2]=temp2Matrix[2][3]=1;

        temp2Matrix[3][2]=1;

        ll temp3Matrix[4][4];

        mem(temp3Matrix,0);

        rep(i,1,3){

            rep(j,1,3){

                rep(k,1,3){

                    temp3Matrix[i][j]=(temp3Matrix[i][j]+tempMatrix[i][k]*temp2Matrix[k][j])%mol;

                }

            }

        }

        rep(i,1,3){

            rep(j,1,3){

                matrix[i][j]=temp3Matrix[i][j];

            }

        }

    }

}

ll solve(int k){ //calc Sk

    ll s2=2,f2=1,f1=1;

    matrixSolve(k-2);

    ll sk=(matrix[1][1]*s2+matrix[1][2]*f2+matrix[1][3]*f1)%mol;

    return sk;

}

int main(){

    while(cin>>n>>k){

        ans=0;

        rep(i,1,n){

            scanf("%d",&a[i]);

            ans=(ans+a[i])%mol;

        }

        sort(a+1,a+1+n);

        if(k==1){

           ans=(ans+a[n-1])%mol;

           ans=(ans+a[n])%mol;

           printf("%I64d\n",ans);

        }

        else{

            int xx=a[n-1];

            int yy=a[n];

            ll ans1=(solve(k)*(ll)xx)%mol;

            ll ans2=((solve(k+1)-1)*(ll)yy)%mol;

            ans=(ans+ans1+ans2)%mol;

            printf("%I64d\n",ans);

        }

    }

    return 0;

}

巴特西

hdu 5171 GTY's birthday gift（数学，矩阵快速幂）

最新文章

热门文章