首页 > 代码库 > bzoj1297: [SCOI2009]迷路(矩阵乘法+拆点)

bzoj1297: [SCOI2009]迷路(矩阵乘法+拆点)

2024-08-17 13:22:28   225人阅读

      题目大意：有向图里10个点，点与点之间距离不超过9，问从1刚好走过T距离到达n的方案数。

       当时看到这题就想到了某道奶牛题(戳我)。这两道题的区别就是奶牛题问的是走T条边，这道题是每条边都有一个边权求走过T边权的方案数。。。所以可以看成奶牛题相当于这一题里的边权为1的情况。

      首先边权为1就把奶牛题的floyd那段改成矩乘就可以了，那么接下来考虑边权不为1的情况，因为边权最多为9，我们就可以把每个点拆成9个点，x[1]~x[9]为x拆完的点，x[i]和x[i+1]连一条边权为1的边，然后x到y有一条边权为z的边，那么就把x的第z个点往y的第1个点连一条边，当然也可以把x[i]和x[i-1]连边然后把x的第一个点往y的第z个点连边，都是等价的，因为x跑到y第z个点再跑回y和x跑z个点再到y所走过的都是z个点。然后跑矩乘就可以辣。

代码如下：

技术分享 
type
  map=array[0..233,0..233]of longint;
var
  n,m,t,i,j,x:longint;
  ch:char;
  mapp,a:map;

function pos(i,j:longint):longint;
begin
  exit((j-1)*m+i);
end;

procedure merge(var x,y:map);
var
  i,j,k:longint;
  z:map;
begin
  fillchar(z,sizeof(z),0);
  for i:=1 to n do
  for j:=1 to n do
  for k:=1 to n do
  z[i,j]:=(z[i,j]+x[i,k]*y[k,j])mod 2009;
  x:=z;
end;

procedure qp(y:longint);
var
  x:map;
begin
  x:=mapp;
  while y>0 do
  begin
    if y and 1=1 then merge(a,x);
    merge(x,x);
    y:=y>>1;
  end;
end;

begin
  readln(m,t);
  n:=m*9;
  for i:=1 to m do
  for j:=1 to 8 do
  mapp[pos(i,j),pos(i,j+1)]:=1;
  for i:=1 to m do
  begin
    for j:=1 to m do
    begin
      read(ch);x:=ord(ch)-ord(‘0‘);
      if x=0 then continue;
      mapp[pos(i,x),j]:=1;
    end;
    readln;
  end;
  for i:=1 to n do
  a[i,i]:=1;
  qp(t);
  writeln(a[1,m]);
end.
View Code

 

bzoj1297: [SCOI2009]迷路(矩阵乘法+拆点)


联系
我们