[原创]玲珑OJ 1109 Niro plays with snow [递推+预处理矩阵乘法]【数学】
2017-03-20 13:37:14 Tabris_ 阅读数:296
博客爬取于2020-06-14 22:41:10
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。https://blog.csdn.net/qq_33184171/article/details/64124556
题目链接:http://www.ifrog.cc/acm/problem/1109 ———————————————————————————————————————————— 1109 - Niro plays with snow Time Limit:2s Memory Limit:128MByte
Submissions:50Solved:8
DESCRIPTION Ah, it snows.
Niro picks up a snowflake. It grows every second. At every second, each of the smallest triangles splits and one of the two rotates by 180 degrees. The process is shown below. In the picture, blue represents the areas that are one layer thick, red two layers thick, yellow three layers thick, and green four layers thick.
Now letF ( n ) F(n) F ( n ) be the number of smallest triangles that are one layers thick at ordern n n , andG ( n ) G(n) G ( n ) be the number of smallest triangles thar are three layers thick at ordern n n . For example,F ( 1 ) = 1 , G ( 1 ) = 0 , F ( 2 ) = 6 , G ( 2 ) = 0 , F ( 3 ) = 30 , G ( 3 ) = 6 , F ( 4 ) = 138 , G ( 4 ) = 78. F(1) = 1, G(1) = 0, F(2) = 6, G(2) = 0, F(3) = 30, G(3) = 6, F(4) = 138, G(4) = 78. F ( 1 ) = 1 , G ( 1 ) = 0 , F ( 2 ) = 6 , G ( 2 ) = 0 , F ( 3 ) = 30 , G ( 3 ) = 6 , F ( 4 ) = 138 , G ( 4 ) = 78.
Givenn n n , can you tell NiroF ( n ) F(n) F ( n ) andG ( n ) G(n) G ( n ) modulo 1234321237?
INPUT T+1 lines. The first line contains one integer T, the number of test cases. Each of the following T lines contains one integer n.
OUTPUT T lines. Each line contains two integers,F ( n ) m o d 1234321237 F(n) \mod 1234321237 F ( n ) mod 1234321237 andG ( n ) m o d 1234321237 G(n) \mod 1234321237 G ( n ) mod 1234321237 for each query.
SAMPLE INPUT 5 3 4 5 52 100
SAMPLE OUTPUT 30 6 138 78 606 654 540534048 39147304 978578590 88026038
HINT1 ≤ T ≤ 1 0 5 1≤T≤10^5 1 ≤ T ≤ 1 0 5 1 ≤ n ≤ 1 0 1 8 1≤n≤10^18 1 ≤ n ≤ 1 0 1 8 ———————————————————————————————————————————— 题目大意: 就是问你 第n个图形中 一层 和三层的三角形有多少个
解题思路:
看了看数据范围,想到是个矩阵乘法,也推出了8 ∗ 8 8*8 8 ∗ 8 的矩阵乘法 $ \left[\begin{array}{cc}\ 0&&6&&0&&0&&0&&0&&0&&0 \0&&3&&2&&0&&1&&0&&0&&0 \0&&1&&2&&1&&2&&0&&0&&0 \0&&0&&0&&3&&3&&0&&0&&0 \0&&0&&0&&0&&0&&6&&0&&0 \0&&0&&0&&0&&0&&3&&2&&0 \0&&0&&0&&0&&0&&1&&2&&1 \0&&0&&0&&0&&0&&0&&0&&3 \\end{array}\right]\times \left[\begin{array}{cc} F_0(i)\F_1(i)\F_2(i)\F_3(i)\G_0(i)\G_1(i)\G_2(i)\G_3(i)\ \end{array}\right] = \left[\begin{array}{cc} F_0(i+1)\F_1(i+1)\F_2(i+1)\F_3(i+1)\G_0(i+1)\G_1(i+1)\G_2(i+1)\G_3(i+1) \end{array}\right]$
-其中F i ( ) F_i() F i ( ) 表示三角形三边中有i i i 条变邻近红色(两层) -其中G i ( ) G_i() G i ( ) 表示三角形三边中有i i i 条变邻近红色(两层)
然而交上去就TLE了, 复杂度O ( T × log 2 3 ( n ) ) O(T\times \log_2^{3}(n)) O ( T × log 2 3 ( n )) …
然后听了Q 的说法 预处理出所有的A矩阵的2 i 2^i 2 i 次幂 然后在计算的时候只要用向量乘上矩阵就好了 复杂度就变成了O ( T × log 2 2 ( n ) ) O(T\times \log_2^{2}(n)) O ( T × log 2 2 ( n )) 然后就过了
然而当时听说还有用4*4的矩阵过得… 最后看了题解 ,真是玄妙无比啊…有兴趣的戳一下题解的传送阵
附本题代码 ————————————————————————————————————————————
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 # include <bits/stdc++.h> using namespace std; typedef long long int LL; # define abs(x) ((x)>0?(x):-(x)) const int MOD = 1234321237; const int N = 1e5+7 ; const int M = 8 ; /********************************************/ struct Matrix{ LL m[M][M]; void clearO(){ for(int i=0; i<M; i++) //初始化矩阵 for(int j=0; j<M; j++) m[i][j]= 0; } void clearE(){ for(int i=0; i<M; i++) //初始化矩阵 for(int j=0; j<M; j++) m[i][j]= (i==j); } void display(){ for(int i=0; i<M; i++){ for(int j=0; j<M; j++) printf("%d ",m[i][j]); puts(""); } puts("-----"); } }; Matrix operator * (Matrix &a,Matrix &b){ Matrix c; c.clearO(); for(int k=0; k<M; k++) for(int i=0; i<M; i++){ //实现矩阵乘法 if(a.m[i][k] <= 0) continue; for(int j=0; j<M; j++){ if(b.m[k][j] <= 0) continue; c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD; } } return c; } Matrix operator ^ (Matrix &a,LL b){ Matrix c; c.clearE(); while(b){ if(b&1) c= c * a ; b >>= 1; a = a * a ; } return c; } Matrix a[100]; void init(){ a[0].m[0][1]=6; a[0].m[1][1]=3,a[0].m[1][2]=2,a[0].m[1][4]=1; a[0].m[2][1]=1,a[0].m[2][2]=2,a[0].m[2][3]=1,a[0].m[2][4]=2; a[0].m[3][1]=0,a[0].m[3][2]=0,a[0].m[3][3]=3,a[0].m[3][4]=3; a[0].m[4][5]=6; a[0].m[5][5]=3,a[0].m[5][6]=2; a[0].m[6][5]=1,a[0].m[6][6]=2,a[0].m[6][7]=1; a[0].m[7][5]=0,a[0].m[7][6]=0,a[0].m[7][7]=3; for(int i=1;(1ll<<i)<=1e18;i++) a[i]=a[i-1]*a[i-1]; } int main(){ init(); int _; Matrix b,c,d; LL n ; scanf("%d",&_); for(int i=1;i<=_;i++){ scanf("%lld",&n);n--; b.clearO(); b.m[0][0]=1; // b.display(); for(int i=0;(1ll<<i)<=n;i++){ if(n&(1ll<<i)){ for(int j=0;j<M;j++){ for(int k=0;k<M;k++){ b.m[1][j]=(b.m[1][j]+b.m[0][k]*a[i].m[k][j]+MOD)%MOD; } } for(int j=0;j<M;j++){ b.m[0][j]=b.m[1][j]; b.m[1][j]=0; } } } printf("%lld " ,((b.m[0][0]+b.m[0][1])%MOD+(b.m[0][2]+b.m[0][3])%MOD)%MOD); printf("%lld\n",((b.m[0][4]+b.m[0][5])%MOD+(b.m[0][6]+b.m[0][7])%MOD)%MOD); } return 0; }