首页 > 代码库 > poj 3734 Blocks
poj 3734 Blocks
从左边开始染色，到第$i$个方块为止，红绿都是偶数的方案数为$a_i$，红绿恰有一个是偶数的方案为$b_i$，红绿都是奇数的方案为$c_i$，从而有如下状态转移方程：
$a_{i+1} = 2 \times a_i + b_i$
$b_{i+1} = 2 \times a_i + 2 \times b_i + 2 \times c_i$
$c_{i+1} = b_i + 2 \times c_i$
从而可以用矩阵表示：
\begin{equation} \left( \begin{array}{c} a_i \\ b_i \\ c_i \end{array} \right) = \left( \begin{array}{ccc} 2 & 1 & 0 \\ 2 & 2 & 2 \\ 0 & 1 & 2 \end{array} \right)^i \left( \begin{array}{c} 1\\ 0\\ 0\\ \end{array} \right) \end{equation}
最终使用矩阵的快速幂即可求解。
1 #define MOD 10007 2 #define M 3 3 #include <cstdio> 4 #include <cstdlib> 5 #include <iostream> 6 #include <cstring> 7 int N; 8 using namespace std; 9 class Matrix10 {11 public:12 int a[M][M];13 Matrix(bool init = 0)14 {15 memset(a, 0, sizeof(a));16 if( init == 1 )17 {18 for( int i = 0 ; i < M ; i++ )19 {20 a[i][i] = 1;21 }22 }23 }24 int * operator [](int i)25 {26 return a[i];27 }28 const int * operator [](int i)const29 {30 return a[i];31 }32 };33 Matrix A;34 void add(int &a, int b)35 {36 a += b;37 while( a >= MOD )38 {39 a -= MOD;40 }41 }42 Matrix operator * (const Matrix &a, const Matrix &b)43 {44 Matrix c;45 for( int i = 0 ; i < M ; i++ )46 {47 for( int j = 0 ; j < M ; j++ )48 {49 for( int k = 0 ; k < M ; k++ )50 {51 add(c[i][k], 1ll * a[i][j] * b[j][k] %MOD);52 }53 }54 }55 return c;56 }57 Matrix quick_pow(Matrix m, int n)58 {59 Matrix ans(1);60 while( n )61 {62 if( n & 1 )63 {64 ans = ans * m;65 }66 n = n>>1;67 m = m * m;68 }69 return ans;70 }71 void solve()72 {73 Matrix ans;74 ans = quick_pow(A, N);75 printf ( "%d\n", ans[0][0]);76 }77 int main(int argc, char *argv[])78 {79 int T;80 scanf ( "%d", &T );81 A[0][0] = 2, A[0][1] = 1;82 A[1][0] = 2, A[1][1] = 2, A[1][2] = 2;83 A[2][1] = 1, A[2][2] = 2;84 while( T-- )85 {86 scanf ( "%d", &N );87 solve();88 }89 }
poj 3734 Blocks
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。