POJ 3734 -- Blocks

POJ 3734 -- Blocks

Description

Panda has received an assignment of painting a line of blocks. Since Panda is such an intelligent boy, he starts to think of a math problem of painting. Suppose there are N blocks in a line and each block can be paint red, blue, green or yellow. For some myterious reasons, Panda want both the number of red blocks and green blocks to be even numbers. Under such conditions, Panda wants to know the number of different ways to paint these blocks.

Input

The first line of the input contains an integer T(1≤T≤100), the number of test cases. Each of the next T lines contains an integer N(1≤N≤10^9) indicating the number of blocks.

Output

For each test cases, output the number of ways to paint the blocks in a single line. Since the answer may be quite large, you have to module it by 10007.

Sample Input

2
1
2

Sample Output

2
6

给定待粉刷的n个墙砖(排成一行)，每个墙砖可以粉刷的颜色种类为:红、蓝、绿、黄，

问粉刷完毕后，红色墙砖和蓝色墙砖都是偶数的粉刷方式有多少种(结果对10007取余).

解题思路:

思路用的是递推.假设粉刷到第i个墙砖时，使用的红色墙砖和蓝色墙砖都是偶数的方案

数有ai，使用的红色和蓝色墙砖一奇一偶的方案数为bi，使用的红色和蓝色墙砖都是奇数的

方案数为ci，那么，我们容易得到下面的递推式:

看到上式，对于学过线代的人来说一定不陌生，我们可以将其写成矩阵的形式，然后会发现该

递推式是等比数列的形式.

对于求取ai，我们可通过计算相应矩阵的幂得知，计算矩阵的幂，利用快速二分幂，

可将时间复杂度降为O(lgn).

1. vector<vector<int> > multi(vector<vector<int> > &A, vector<vector<int> > &B)  
2. {  
3.     vector<vector<int> > C(A.size(), vector<int>(B[0].size()));  
4.     for (unsigned i = 0; i != A.size(); ++i)  
5.         for (unsigned j = 0; j != B[0].size(); ++j)  
6.             for (unsigned k = 0; k != B.size(); ++k)  
7.                 C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % M;  
8.     return C;  
9. }  
10. //二分快速幂  
11. vector<vector<int> > power(vector<vector<int> > &A, int n)  
12. {  
13.     vector<vector<int> > B(A.size(), vector<int>(A.size()));  
14.     for (int i = 0; i != A.size(); ++i)  
15.         B[i][i] = 1;  
16.     while (n)  
17.     {  
18.         if (n & 1)  
19.             B = multi(B, A);  
20.         A = multi(A, A), n >>= 1;  
21.     }  
22.     return B;  
23. }  
24. int main()  
25. {  
26.     int t,n;  
27.     cin >> t;  
28.     while (t--)  
29.     {  
30.         vector<vector<int> > A(3, vector<int>(3));  
31.         A[0][0] = 2, A[0][1] = 1, A[0][2] = 0;  
32.         A[1][0] = 2, A[1][1] = 2, A[1][2] = 2;  
33.         A[2][0] = 0, A[2][1] = 1, A[2][2] = 2;  
34.         cin >> n;  
35.         A = power(A, n);  
36.         cout << A[0][0] << endl;  
37.     }  
38.     return 0;  
39. }  

Read full article from 3734 -- Blocks