首页 > 代码库 > POJ 3734

POJ 3734


题目的大意:


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


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


解题思路:


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


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


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



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


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




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


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


解题代码:


#include<vector>
#include<iostream>
#include<algorithm>
#define M 10007
using namespace std;
//矩阵乘法
vector<vector<int> > multi(vector<vector<int> > &A, vector<vector<int> > &B)
{
    vector<vector<int> > C(A.size(), vector<int>(B[0].size()));
    for (unsigned i = 0; i != A.size(); ++i)
        for (unsigned j = 0; j != B[0].size(); ++j)
            for (unsigned k = 0; k != B.size(); ++k)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % M;
    return C;
}
//二分快速幂
vector<vector<int> > power(vector<vector<int> > &A, int n)
{
    vector<vector<int> > B(A.size(), vector<int>(A.size()));
    for (int i = 0; i != A.size(); ++i)
        B[i][i] = 1;
    while (n)
    {
        if (n & 1)
            B = multi(B, A);
        A = multi(A, A), n >>= 1;
    }
    return B;
}
int main()
{
    int t,n;
    cin >> t;
    while (t--)
    {
        vector<vector<int> > A(3, vector<int>(3));
        A[0][0] = 2, A[0][1] = 1, A[0][2] = 0;
        A[1][0] = 2, A[1][1] = 2, A[1][2] = 2;
        A[2][0] = 0, A[2][1] = 1, A[2][2] = 2;
        cin >> n;
        A = power(A, n);
        cout << A[0][0] << endl;
    }
    return 0;
}