POJ 3734 DP+矩阵乘法

题意：

给n个block涂4种颜色，要求其中red和green的block为偶数，其余随意。输出方案总数

 

思路：
递推，设dp[i][j][k] 表示前i个block ，有j个red，k个green，的方案总数

又因为j,k不是奇数就是偶数，可以简化j,k=1则表示奇数，j,k=0表示偶数

就可以递推了~

用矩阵递推更有效率~

def=

{{2,0,1,1},

  {0,2,1,1},

  {1,1,2,0},

  {1,1,0,2}

}

ans[0]={0,1,0,0}

ans[i]=def^k*ans[i-1]

注意：矩阵乘法不满足交换律。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>

#define SIZE 110
#define mod 10007

using namespace std;

struct MT
{
    int x,y;
    int mt[SIZE][SIZE];
}ans,def;

int n,tt;

inline MT operator *(MT a,MT b)
{
    MT c;
    memset(c.mt,0,sizeof c.mt);
    c.x=a.x; c.y=b.y;
    for(int i=1;i<=a.x;i++)
        for(int j=1;j<=b.y;j++)
            for(int k=1;k<=a.y;k++)
                c.mt[i][j]=(c.mt[i][j]+(a.mt[i][k]%mod)*(b.mt[k][j]%mod))%mod;
    return c;
}

void read()
{
    scanf("%d",&n);
    ans.mt[1][1]=ans.mt[3][1]=ans.mt[4][1]=0; ans.mt[2][1]=1;
    ans.x=4; ans.y=1;
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
            def.mt[i][j]=1;
    for(int i=1;i<=4;i++) def.mt[i][i]=2;
    def.mt[1][2]=def.mt[2][1]=def.mt[3][4]=def.mt[4][3]=0;
    def.x=def.y=4;
}

void go()
{
    while(n)
    {
        if(n&1) ans=def*ans;
        def=def*def;
        n>>=1;
    }
    printf("%d\n",ans.mt[2][1]);
}

int main()
{
    scanf("%d",&tt);
    while(tt--)
    {
        read();
        go();
    }
    system("pause");
    return 0;
}