poj 3734 Blocks DP+矩阵快速幂

缘起

日常浪费生命~ poj 3734 Blocks

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
给定n个方块排成一列, 现在要用红蓝绿黄四种颜色给这些方块染色. 求染成颜色中红色、绿色的数量为偶数的
方案数量. 输出对10007取余。

【输入】
多样例. 第一行是样例数. 每个样例一个N（1≤N≤10^9）

【输出】
每个样例输出答案

【样例输入】
2
1
2

【样例输出】
2
6

【限制】
1s

这种题目就是搞出一个线性的dp公式. 然后转乘矩阵，然后就是矩阵快速幂了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
令 a[n]是红偶绿偶, b[n]是红奇绿偶, c[n]是红偶绿奇,d[n]是红奇绿奇. 则根据第一个block染的颜色分别为
红蓝绿黄, 得到如下dp公式
a[n]=2a[n-1]+b[n-1]+c[n-1]
b[n]=a[n-1]+2b[n-1]+d[n-1]
c[n]=a[n-1]+2c[n-1]+d[n-1]
d[n]=b[n-1]+c[n-1]+2d[n-1]
转换成矩阵就是, 令列向量x[n]=(a[n],b[n],c[n],d[n])^T, 则
x[1]=(2,1,1,0)
A=
{2,1,1,0}
{1,2,0,1}
{1,0,2,1}
{0,1,1,2}
所以答案是A^{n-1}*x[1], 对于 A^{n-1}我们显然可以套用矩阵快速幂模板

于是我们可以ac了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

int n,x[4], xx[4]={2,1,1,0},a[4][4], aa[4][4]={{2,1,1,0},{1,2,0,1},{1,0,2,1},{0,1,1,2}},M=10007;

void m_mul(int y[4][4], int z[4][4]) // 矩阵乘法 y*z
{
	int ans[4][4];
	memset(ans, 0, sizeof(ans));
	for (int i = 0; i<4; i++)
	{
		for (int j= 0; j<4; j++) // 决定ans[i][j]
		{
			for (int k = 0; k<4; k++)
			{
				ans[i][j]+=y[i][k]*z[k][j];
				ans[i][j]%=M;
			}
			ans[i][j]%=M; // 保证最后乘法之后y中每个元素都<M
		}
	}
	memcpy(y, ans, sizeof(ans)); // 不要写 sizeof(y), y只是一个行指针~
}

void ksm(int a[4][4], int b) // 矩阵快速幂 a^b
{
	int ans[4][4];
	for (int i = 0; i<4; i++)
	{
		for (int j = 0; j<4; j++)
		{
			ans[i][j]=i==j;
		}
	} // 初始为单位矩阵
	while(b)
	{
		if (b&1)
		{
			m_mul(ans, a);
		}
		if (b>1)
		{
			m_mul(a,a);
		}
		b>>=1;
	}
	memcpy(a,ans, sizeof(ans));
}

void kk(int a[4][4], int x[4])
{
	int ans[4];
	memset(ans, 0, sizeof(ans));
	for (int i = 0; i<4; i++)
	{
		for (int j = 0; j<4; j++)
		{
			ans[i] += a[i][j]*x[j];
		}
	}
	memcpy(x,ans, sizeof(ans));
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		scanf("%d", &n);
		--n;
		memcpy(a,aa, sizeof(a));
		ksm(a, n);
		memcpy(x,xx,sizeof(x));
		kk(a,x);
		printf("%d\n",x[0]%M); // 保险起见, 最后再mod一次
	}
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 116kB
Length 1317
Lang C++
Submitted 2019-09-20 08:28:52
Shared
RemoteRunId 20877496