锐客网

  1. 首页 > 睿知 > it技术 > >

HDU 6030 Happy Necklace

IT知识necklacehappy

不飞则已，一飞冲天；不鸣则已，一鸣惊人。这篇文章主要讲述HDU 6030 Happy Necklace相关的知识，希望能为你提供帮助。
【HDU 6030 Happy Necklace】矩阵快速幂。

#include < bits/stdc++.h> using namespace std; const long long mod=1e9+7; const long long inf=1e18; int T; long long n; struct Matrix { long long A[5][5]; int R, C; Matrix operator*(Matrix b); }; Matrix X, Y, Z; Matrix Matrix::operator*(Matrix b) { Matrix c; memset(c.A, 0, sizeof(c.A)); int i, j, k; for (i = 1; i < = R; i++) for (j = 1; j < = C; j++) for (k = 1; k < = C; k++) c.A[i][j] = (c.A[i][j] + (A[i][k] * b.A[k][j])%mod)%mod; c.R=R; c.C=b.C; return c; }void init() { n = n - 2; memset(X.A,0,sizeof X.A); memset(Y.A,0,sizeof Y.A); memset(Z.A,0,sizeof Z.A); Z.R = 1; Z.C = 3; Z.A[1][1]=1; Z.A[1][2]=1; Z.A[1][3]=1; for(int i=1; i< =3; i++) Y.A[i][i]=1; Y.R = 3; Y.C = 3; X.A[1][1]=1; X.A[1][2]=0; X.A[1][3]=1; X.A[2][1]=1; X.A[2][2]=0; X.A[2][3]=0; X.A[3][1]=0; X.A[3][2]=1; X.A[3][3]=0; X.R = 3; X.C = 3; }void work() { while (n) { if (n % 2 == 1) Y = Y*X; n = n > > 1; X = X*X; } Z = Z*Y; printf("%lld\n", (Z.A[1][1]+Z.A[1][2]+Z.A[1][3])%mod); }int main() { scanf("%d",& T); while(T--) { scanf("%lld",& n); init(); work(); } return 0; }

 

    推荐阅读


    上一篇：Android_1.1

    下一篇：Android KK后为何工厂模式下无法adb 无法重新启动机器 （）