POJ 3734 (矩阵快速幂+染色问题)

题意：

有n个方格排成一排，现在有四种颜色，红蓝绿黄，问红色和绿色方格同时为偶
数的排列方式有多少种。
思路：
其实方格的状态可以分为三种，a ： 红色和绿色方格都为偶数，b：红色和绿色
方格其中刚好有一种方格是偶数，c红色和绿色方格都是奇数。

则有：a(i+1) = a(i)*2 + b(i); b(i+1) = a(i)*2 + b(i)*2 + c(i)*2 ;
c(i+1) = b(i) + c(i)*2

则可以列出矩阵表达式。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 10;
int a[MAXN][MAXN];
int ans[MAXN][MAXN];
int temp[MAXN][MAXN];
int mod = 10007;
void mult(int a[][MAXN],int b[][MAXN],int n)
{
memset(temp,0,sizeof(temp));
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n; j++)
for(int k = 1;k <= n; k++)
temp[i][j] = (temp[i][j] + a[i][k]*b[k][j])%mod;
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n; j++)
a[i][j] = temp[i][j];
}
void Pow(int a[][MAXN],int n)
{
memset(ans,0,sizeof(ans));
ans[1][1] = ans[2][2] = ans[3][3] = 1;
while(n) {
if(n&1)
mult(ans,a,3);
mult(a,a,3);
n = n>>1;
}
}
int main()
{
//freopen("in.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--) {
a[1][1] = 2,a[1][2] = 1,a[1][3] = 0;
a[2][1] = 2,a[2][2] = 2,a[2][3] = 2;
a[3][1] = 0,a[3][2] = 1,a[3][3] = 2;
int n;
scanf("%d",&n);
Pow(a,n);
printf("%dn",ans[1][1]);
}
return 0;
}

最后

以上就是能干石头为你收集整理的POJ 3734 (矩阵快速幂+染色问题)的全部内容，希望文章能够帮你解决POJ 3734 (矩阵快速幂+染色问题)所遇到的程序开发问题。

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