题意: 个 n 个方块涂色, 只能涂红黄蓝绿四种颜色, 求最终红色和绿色都为偶数的方案数.
该题我们可以想到一个递推式 . 设 a[i] 表示到第 i 个方块为止红绿是偶数的方案数, b[i] 为红绿恰有一个是偶数的方案数, c[i] 表示红绿都是奇数的方案数.
那么有如下递推可能:
递推 a[i+1]:1. 到第 i 个为止都是偶数, 且第 i+1 个染成蓝或黄; 2. 到第 i 个为止红绿恰有一个是奇数, 并且第 i+1 个方块染成了奇数对应的颜色.
递推 b[i+1]:1. 到第 i 个为止都是偶数, 且第 i+1 个染成红或绿; 2. 到第 i 个为止红绿恰有一个是奇数, 并且第 i+1 个方块染成了蓝或黄; 3. 到第 i 个方块为止红火绿都是奇数, 并且第 i+1 个染成红火绿.
递推 c[i+1]:1. 到第 i 个为止红绿恰有一个是奇数, 并且第 i+1 个方块染成偶数对应的颜色; 2. 到第 i 个为止红绿都是奇数, 并且第 i+1 个方块染成蓝或黄.
即 a[i+1] = 2*a[i] + b[i];
- b[i+1] = 2*a[i] + 2*b[i] + 2*c[i];
- c[i+1] = b[i] + 2*c[i];
因为 DP 的过程中, 每一步都是在重复上一个过程, 所以可以用矩阵相乘来优化算法.
将上述递推式写成矩阵相乘的形式:
- { a[i] } {2 1 0}^i{a[0] }
- { b[i] } = {2 2 2} {b[0] }
- { c[i] } {0 1 2} {c[0] }
然后用矩阵快速幂就可以了.
AC 代码
- #include<stdio.h>
- #include<string.h>
- #define mod 10007
- struct Mat
- {
- long long mat[3][3];
- };
- Mat operator * (Mat a,Mat b)
- {
- int n=3;
- Mat c;
- c.mat[2][2]=c.mat[2][0]=c.mat[2][1]=c.mat[0][0]=c.mat[0][1]=c.mat[0][2]=c.mat[1][0]=c.mat[1][1]=c.mat[1][2]=0;
- int i,j,k;
- for(k =0 ; k <n ; k++)
- {
- for(i = 0 ; i < n ;i++)
- {
- if(a.mat[i][k]==0) continue;// 优化
- for(j = 0 ;j < n ;j++)
- {
- if(b.mat[k][j]==0) continue;// 优化
- c.mat[i][j] = (c.mat[i][j]+(a.mat[i][k]*b.mat[k][j])%mod)%mod;
- }
- }
- }
- return c;
- }
- Mat operator ^(Mat a,int k)
- {
- int n=3;
- Mat c;
- int i,j;
- for(i =0 ; i < n ;i++)
- for(j = 0; j < n ;j++)
- c.mat[i][j] = (i==j);
- for(; k ;k>>= 1)
- {
- if(k&1) c = c*a;
- a = a*a;
- }
- return c;
- }
- int main( )
- {
- long long n;
- int t;
- scanf("%d",&t);
- while(t--)
- {
- scanf("%lld",&n);
- Mat A;
- A.mat[0][0]=2;A.mat[0][1]=1;A.mat[0][2]=0;
- A.mat[1][0]=2;A.mat[1][1]=2;A.mat[1][2]=2;
- A.mat[2][0]=0;A.mat[2][1]=1;A.mat[2][2]=2;
- Mat ans=A^n;
- printf("%lld\n",ans.mat[0][0]);
- }
- return 0;
- }
- View Code
- POJ 3734 Blocks(矩阵快速幂 + 矩阵递推式)
来源: http://www.bubuko.com/infodetail-2635158.html