这是yhc大牛矩乘论文上的题目,那里面分析得很清楚了
这里就说说我一开始错的地方,我一开始处理每个时刻能通过的邻接矩阵的时候
把以不能访问的点i为起点和终点的都标记为0了,实际上只能标记以i为终点的边即可
很好理解,是自己太脑残了

 const mo=;
var b,c,g,f:array[..,..] of longint;
v:array[..,..] of boolean;
w,d:array[..] of longint;
a:array[..,..,..] of longint;
fish,i,j,k,x,y,n,m,s,e,t:longint; procedure work(i:longint);
var j,k:longint;
begin
a[i]:=f;
for j:= to n do
if v[j,i] then
begin
for k:= to n do
a[i,k,j]:=;
end;
end; procedure mul(p:longint);
var i,j,k:longint;
begin
b:=c;
for i:= to n do
for j:= to n do
begin
c[i,j]:=;
for k:= to n do
c[i,j]:=(c[i,j]+b[i,k]*a[p,k,j] mod mo) mod mo;
end;
end; procedure time;
var i,j,k:longint;
begin
for i:= to n do
for j:= to n do
begin
c[i,j]:=;
for k:= to n do
c[i,j]:=(c[i,j]+g[i,k]*f[k,j] mod mo) mod mo;
end;
end; procedure quick(x:longint);
var i,j:longint;
begin
j:=;
while x> do
begin
inc(j);
d[j]:=x mod ;
x:=x shr ;
end;
fillchar(c,sizeof(c),);
for i:= to n do
c[i,i]:=;
for i:=j downto do
begin
g:=c;
f:=c;
time;
if d[i]= then
begin
g:=c;
f:=b;
time;
end;
end;
end; begin
readln(n,m,s,e,t);
inc(s);
inc(e);
for i:= to m do
begin
readln(x,y);
inc(x);
inc(y);
f[x,y]:=;
f[y,x]:=;
end;
readln(fish);
for i:= to fish do
begin
read(y);
for j:= to y- do
begin
read(x);
inc(x);
k:=j;
while k<= do
begin
v[x,k]:=true;
k:=k+y;
end;
end;
end;
for i:= to do
work(i);
if t< then
begin
c:=a[];
for i:= to t do
mul(i);
end
else begin
c:=a[];
for i:= to do
mul(i);
b:=c;
quick(t div );
for i:= to t mod do
mul(i);
end;
writeln(c[s,e]);
end.
04-24 17:51