当前位置：首页 > news >正文

河南省汝州市文明建设网站/南宁seo排名外包

news 2025/8/12 15:43:50

河南省汝州市文明建设网站,南宁seo排名外包,淄博学校网站建设报价,成都市制作企业网站...起床了先把这题给过了还是今天凌晨留下来的.... 刚开始真sb啊以为矩阵构造出来不能进行快速幂运算的一定要借助单位矩阵..... 一般你构造出来的时候 2个矩阵的行列不是全都相等的为了方便运算我们可以空余位置默认为0 反正我是这样解决的 ....好像这个解决方法有点渣…

...起床了先把这题给过了还是今天凌晨留下来的....

刚开始真sb啊以为矩阵构造出来不能进行快速幂运算的一定要借助单位矩阵.....

一般你构造出来的时候 2个矩阵的行列不是全都相等的为了方便运算我们可以空余位置默认为0

反正我是这样解决的 ....好像这个解决方法有点渣我也不清楚...

　　　　touch me

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 const int mod = 2009;
 6 
 7 struct data
 8 {
 9     int m[4][4];
10 }base,result;
11 
12 void init( )
13 {
14     memset( base.m , 0 , sizeof(base.m) );
15     base.m[0][1] = base.m[1][2] = base.m[3][0] = base.m[3][3] = 1;
16     base.m[2][0] = 7;
17     base.m[2][1] = 2;
18     base.m[2][2] = 3;
19     
20     memset( result.m , 0 , sizeof(result.m) );
21     result.m[0][0] = 1;
22     result.m[1][0] = 3;
23     result.m[2][0] = 5;
24     result.m[3][0] = 0;
25 }
26 
27 data multi( data& p , data& q )//p--base q--result
28 {
29     data temp;
30     for( int i = 0 ; i<4 ; i++ )
31     {
32         for( int j = 0 ; j<4 ; j++ )
33         {
34             temp.m[i][j] = 0;
35             for( int k = 0 ; k<4 ; k++ )
36             {
37                 temp.m[i][j] = ( temp.m[i][j] + p.m[i][k]*q.m[k][j] ) %mod;
38             }
39         }
40     }
41     return temp;
42 }
43 
44 int fastMod( int n )
45 {
46     while( n )
47     {
48         if( n&1 )
49         {
50             result = multi( base , result );
51         }
52         base = multi( base , base );
53         n >>= 1;
54     }
55     return result.m[3][0];
56 }
57 
58 int main()
59 {
60     int t , n;
61     while( cin >> t )
62     {
63         for( int i = 1 ; i<=t ; i++ )
64         {
65             init();
66             cin >> n;
67             cout << "Case " << i << ": " << fastMod(n+1) << endl;
68         }
69     }
70     return 0;
71 }

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 const int mod = 2009;
 6 
 7 struct data
 8 {
 9     int m[4][4];
10     int mat[4][1];
11 }base,result;
12 
13 void init( )
14 {
15     memset( base.m , 0 , sizeof(base.m) );
16     base.m[0][1] = base.m[1][2] = base.m[3][0] = base.m[3][3] = 1;
17     base.m[2][0] = 7;
18     base.m[2][1] = 2;
19     base.m[2][2] = 3;
20     
21     result.mat[0][0] = 1;
22     result.mat[1][0] = 3;
23     result.mat[2][0] = 5;
24     result.mat[3][0] = 0;
25 }
26 
27 data multi( data& p , data& q )//p--base q--result
28 {
29     data temp;
30     for( int i = 0 ; i<4 ; i++ )
31     {
32         for( int j = 0 ; j<1 ; j++ )
33         {
34             temp.mat[i][j] = 0;
35             for( int k = 0 ; k<4 ; k++ )
36             {
37                 temp.mat[i][j] = ( temp.mat[i][j] + p.m[i][k]*q.mat[k][j] ) %mod;
38             }
39         }
40     }
41     return temp;
42 }
43 
44 data mul( data& p , data& q )//p--base q--base
45 {
46     data t;
47     for( int i = 0 ; i<4 ; i++ )
48     {
49         for( int j = 0 ; j<4 ; j++ )
50         {
51             t.m[i][j] = 0;
52             for( int k = 0 ; k<4 ; k++ )
53             {
54                 t.m[i][j] = ( t.m[i][j] + p.m[i][k]*q.m[k][j] ) %mod;
55             }
56         }
57     }
58     return t;
59 }
60 
61 int fastMod( int n )
62 {
63     while( n )
64     {
65         if( n&1 )
66         {
67             result = multi( base , result );
68         }
69         base = mul( base , base );
70         n >>= 1;
71     }
72     return result.mat[3][0];
73 }
74 
75 int main()
76 {
77     int t , n;
78     while( cin >> t )
79     {
80         for( int i = 1 ; i<=t ; i++ )
81         {
82             init();
83             cin >> n;
84             cout << "Case " << i << ": " << fastMod(n+1) << endl;
85         }
86     }
87     return 0;
88 }