bzoj1297

首先学习是学习矩阵乘法在邻接矩阵的应用
ab两点经过k条边的路径数就等于图的邻接矩阵G的k次幂之后G[a,b]的值
但这道题问的是经过长度为k的路径数
考虑到每条边的长度最长只有9，所以我们把一个点拆成9个点，
i1~i9 顺次相连长度为1，i9为出点
对于长度为k的边eij，连边i9-->j(10-k) 长度为1
这样图中的每条边的长度都变成了1，就相当于求k条边的路径数了

 1 const mo=2009;
 2 var ans,a,b,c:array[0..92,0..92] of longint;
 3     d:array[0..30] of longint;
 4     i,j,k,x,n,m:longint;
 5     ch:char;
 6 
 7 procedure mul;
 8   var i,j,k:longint;
 9   begin
10     for i:=1 to n do
11       for j:=1 to n do
12       begin
13         ans[i,j]:=0;
14         for k:=1 to n do
15           ans[i,j]:=(ans[i,j]+a[i,k]*b[k,j] mod mo) mod mo;
16       end;
17    end;
18 
19 procedure quick(x:longint);
20   var i,j,p,q:longint;
21   begin
22     j:=0;
23     while x<>0 do
24     begin
25       inc(j);
26       d[j]:=x mod 2;
27       x:=x shr 1;
28     end;
29     fillchar(ans,sizeof(ans),0);
30     for i:=1 to n do
31       ans[i,i]:=1;
32     for i:=j downto 1 do
33     begin
34       a:=ans;
35       b:=ans;
36       mul;
37       if d[i]=1 then
38       begin
39         a:=ans;
40         b:=c;
41         mul;
42       end;
43     end;
44   end;
45 
46 begin
47   readln(n,m);
48   for i:=1 to n do
49   begin
50     for j:=1 to n do
51     begin
52       read(ch);
53       x:=ord(ch)-48;
54       if x<>0 then
55       begin
56         c[i*9,j*9-x+1]:=1;
57         for k:=j*9-x+1 to j*9-1 do
58           c[k,k+1]:=1;
59       end;
60     end;
61     readln;
62   end;
63   n:=n*9;
64   quick(m);
65   writeln(ans[9,n]);
66 end.
67 
68

View Code