铺砖问题

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