题目链接： Blocks

题意

有N个方块，依次给每个块涂颜色，有红蓝绿黄四种颜色可选，问最后涂完，使得红色和绿色块均为偶数的涂法总共有几种，最终答案mod10007

思路

N可以达到很大，我们需要找到递推关系式子。
我们假设到第i个块的时候，
a[i]代表红绿块均为偶数的涂法数目。
b[i]代表红绿块有一种块为偶数的情况数目。
c[i]代表红绿块均为奇数的情况数目。
那么到第i + 1个块时：
可以得到递推式子：
a[i + 1] = a[i] * 2 + b[i]
b[i + 1] = b[i ]* 2+ a[i ] * 2 + c[i ] * 2
c[i + 1] = c[i] * 2 + b[i]
由此可以得到转移矩阵。
$$\left\{\begin{array}{ccc}2& 1& 0\\ 2& 2& 2\\ 0& 1& 2\end{array}\right\}\times \left\{\begin{array}{c}{a}_i\\ b_i\\ c_i\end{array}\right\}=\left\{\begin{array}{c}{a}_{i+1}\\ b_{i+1}\\ c_{i+1}\end{array}\right\}$$

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
struct Matrix{
   ll m[4][4];
};
const ll mod = 10007;
Matrix mul(Matrix A,Matrix B)
{
   Matrix tmp;
   memset(tmp.m,0,sizeof(tmp.m));
   for(int i = 1; i <= 3 ;i++)
   for(int j = 1; j <= 3 ;j++)
       for(int k = 1; k <= 3 ;k++)
   {
       tmp.m[i][j] = (tmp.m[i][j] + A.m[i][k] * B.m[k][j]) % mod;
       tmp.m[i][j] %= mod;
   }
   return tmp;
}
Matrix pow(Matrix A,ll n)
{
   int i;
   Matrix res;
   memset(res.m,0,sizeof(res.m));
   for(i = 1; i <= 3 ;i++)
       res.m[i][i] = 1;
   while(n)
   {
       if(n & 1)
           res = mul(res,A);
       A = mul(A,A);
       n >>= 1;
   }
   return res;
}
int main()
{
   int T;
   long long n;
   cin >> T;
   while(T--)
   {
       cin >> n;
       Matrix A;
       A.m[1][1] = 2;
       A.m[1][2] = 1;
       A.m[1][3] = 0;
       A.m[2][1] = 2;
       A.m[2][2] = 2;
       A.m[2][3] = 2;
       A.m[3][1] = 0;
       A.m[3][2] = 1;
       A.m[3][3] = 2;
       A = pow(A,n - 1);
       Matrix C;
       C.m[1][1] = 2;
       C.m[2][1] = 2;
       C.m[3][1] = 0;
       C = mul(A,C);
       cout << C.m[1][1] << endl;
   }
}

最后

以上就是迷人小鸭子为你收集整理的POJ -3734(矩阵快速幂)题意思路的全部内容，希望文章能够帮你解决POJ -3734(矩阵快速幂)题意思路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。