铺砖问题

发表于 分类于 ， 阅读次数： 本文字数： 3.6k 阅读时长 ≈ 3 分钟

Description

用1×2的 砖头铺满N*M的区域，不能有重叠，一共有多少种方案？如下图所示：
方式

Data Constraint

20%的数据满足1<=N,M<=6
50%的数据满足1<=N<=100,1<=M<=11
另外50%的数据满足1<=N<=10^200,1<=M<=5

Analysis

对于此题的前50%的数据
可以参照此位大神的解析：
http://blog.csdn.net/yan_____/article/details/8719748
我的程序前50%就是参考了这篇文章

对于100%的数据

  1. 我们发现N很大，但是M却很小。
  2. 前50%的数据我们都是通过不同的二进制状态转移并累加得到的。这种转移就显然就是矩阵自乘的结果。而他的答案就是$a[(1 shl m)-1,(1 shl m)-1]$,表示从(1 shl m)-1转移到(1 shl m)-1的方案数。
  3. 那么我们可以将前50%数据得到的st数组中的对应值映射到[0..1 shl m,0..1 shl m]的矩阵中，然后将这个矩阵自乘n次即可得到答案。
  4. 矩阵自乘可以用快速幂进行优化。
  5. 因为做一次矩阵乘法的时间复杂度为$O(N^3)$。所以整体的时间复杂度为$O((2^m)^3*log(10^100)/log(2))$。
  6. 因为n极其的庞大所以在做快速幂时我们需要用到单精除。
  7. 可能很多人会不理解为什么用矩阵乘法和为什么答案是$a[(1 shl m)-1,(1 shl m)-1]$。(懂得人可以忽略此部分内容)

对于每一层来说，因为st数组中$st[i][0] $都可以到$st[i][1]$ 。所以我们首先想想最简单的情况:
当n=1时，他的答案就是从$dp[0][1 shl m-1]$ 到$dp[1][1 shl m-1] $。就是 $base[1 shl m -1] [1 shl m-1]$。
当n=2 时，我们可以看看矩阵乘法的工作原理 对于答案$ans[i,j] += a[i,k]*a[k,j]$，他是通过枚举k将第i行和第j列一一对应相乘并累加的道德结果。而在我们的基础矩阵base存放的就是第i行的状态可以转移到哪j个状态。当你要从i这个状态到j这个状态，我们可以枚举一个中间点k让i先到k，再从k到j
,这样恰好进行了两次转移所以这个ans矩阵，就代表从第i个状态经过了n次转移(看你乘了多少次)到达第j个状态的方案数。
其实矩阵乘法可以类比floyd求最短路的算法。

Code

因为代码比较丑，所以不要见怪

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
const	maxn=100+5;maxm=10+5;
		mo=1000000007;len=17;size=(1 shl 5);jw=100000000000000000;
type	bignum=array[0..15] of int64;
		matrix=array[0..size,0..size] of int64;
var	i,j,m,n,tot,tmp:longint;
	st:array[0..(1 shl maxm),0..1] of longint;
	dp:array[0..maxn,0..(1 shl maxm)] of int64;
	s,nn,mm:string;
	base,ans:matrix;
	n1:bignum;
	sum:int64;
procedure dfs(n,from,next:longint);
begin
	if (n>m) then begin
		exit;
	end;
	if (n=m) then begin
		st[tot][0]:=from;
		st[tot][1]:=next;
		inc(tot);
		exit;
	end;
	dfs(n+2,(from<<2)+3,(next<<2)+3);
	dfs(n+1,(from<<1)+1,(next<<1));
	dfs(n+1,(from<<1),(next<<1)+1);
end;
procedure div2(var x:bignum);
var	i,t:longint;
begin
	t:=0;
	for i:=x[0] downto 1 do begin
		x[i]:=t*jw+x[i];
		t:=x[i] mod 2;
		x[i]:=x[i] div 2;
		if x[i]=0 then x[0]:=i-1;
	end;
end;
procedure stom(var s:string;var num:bignum);
var	ts:string[len];
	i:longint;
begin
	fillchar(num,sizeof(num),0);
	ts:='';
	for i:=length(s) downto 1 do begin
		ts:=s[i]+ts;
		if length(ts)=len then begin
			inc(num[0]);
			val(ts,num[num[0]]);
			ts:='';
		end;
	end;
	if ts<>'' then begin
		inc(num[0]);
		val(ts,num[num[0]]);
	end;
end;
function mul(x,y:matrix):matrix;//矩阵乘法
var     i,j,k,size1:integer;
	z:matrix;
begin
	size1:=(1<<m);
        fillchar(z,sizeof(z),0);
        for i:=0 to size1 do
        for j:=0 to size1 do
	for k:=0 to size1 do begin
		z[i,j]:=(z[i,j]+x[i,k]*y[k,j])mod mo;
	end;
	exit(z);
end;
procedure work(y:bignum);
begin
	fillchar(ans,sizeof(ans),0);
	for i:=0 to (1<<m) do ans[i][i]:=1;
	//单位矩阵，就是实数中的1
	while (y[0]<>0) do begin
		if odd(y[1]) then begin
			ans:=mul(ans,base);
		end;
		base:=mul(base,base);
		div2(y);
	end;
end;
begin
	readln(s);
	tmp:=pos(' ',s);
	nn:=copy(s,1,tmp-1);
	mm:=copy(s,tmp + 1,length(s) - tmp);val(mm,m);

	tot:=0;
	dfs(0,0,0);
	if (length(nn)<=2) or (nn='100') then begin
		//前50%的做法
		val(nn,n);
		if odd(n*m) then begin
			writeln(0);
			exit;
		end;	

		dp[0][(1<<m)-1]:=1;
		for i:=1 to n do 
			for j:=0 to tot-1 do begin
				dp[i][st[j][1]]:=(dp[i][st[j][1]]+dp[i-1][st[j][0]]) mod mo;
			end;
		writeln(dp[n][(1<<m)-1]);
	end else begin
		fillchar(base,sizeof(base),0);
		for j:=0 to tot-1 do begin
			base[st[j][0]][st[j][1]]:=1;
		end;
		//初始化基础对应矩阵
		stom(nn,n1);//将nn这个字符串转化为高精度数组
		work(n1);//快速幂做矩阵乘法
		sum:=ans[(1<<m)-1][(1<<m)-1];
		writeln(sum mod mo);
	end;
end.

Tips

此题源自：zoj1100
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1100
据说此题有通项公式，具体请看维基百科
https://en.wikipedia.org/wiki/Domino_tiling