/ Vijos / 题库 / 迷宫 /

# 26 条题解

• @ 2018-03-10 10:39:27

虽然不太能够知道大犇是如何一下子看出来矩阵乘法的，但还是惊叹这种方法，算法本身不难，难就难在如何将这个题抽象为矩阵快速幂。

``````import java.util.Scanner;

public class Main {
static int n;
static int m, s, f, p;
static int[][] d, ans;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
d = new int[n + 1][n + 1];
ans = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
ans[i][i] = 1;
for (int j = 1; j <= n; j++) {
d[i][j] = in.nextInt();
}
}
m = in.nextInt();
s = in.nextInt();
f = in.nextInt();
p = in.nextInt();

while (m > 0) {
if (m % 2 == 1) {
ans = chengfa(d, ans);
}
d = chengfa(d, d);
m >>= 1;
}
System.out.println(ans[s][f] % p);
}
private static int[][] chengfa(int[][] a, int[][] b) {
// TODO Auto-generated method stub
int[][] c = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
c[i][j] += a[i][k] * b[k][j];
c[i][j] %= p;
}
}
}
return c;
}

}
``````
• @ 2017-10-24 13:32:29

这道题跟caioj 1486思路很像
http://blog.csdn.net/lixuanjing2016/article/details/77569378

``````#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
struct node
{
int a[55][55];
node()
{
memset(a,0,sizeof(a));
}
};
int n;
node chengfa(node a,node b,int mod)
{
node c;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
}
}
}
return c;
}
int main()
{
scanf("%d",&n);
node pre,ans;
for(int i=1;i<=n;i++)
{
ans.a[i][i]=1;
for(int j=1;j<=n;j++)scanf("%d",&pre.a[i][j]);
}
int x,y,k,mod;
scanf("%d%d%d%d",&k,&x,&y,&mod);
while(k>0)
{
if(k%2==1)ans=chengfa(pre,ans,mod);
pre=chengfa(pre,pre,mod);
k/=2;
}
printf("%d\n",ans.a[x][y]%mod);
return 0;
}
``````
• @ 2015-11-04 22:38:42

矩阵乘法+快速幂

这题的普通做法是递推。令 f[i][j][m] 表示从 i 到 j 走 m 条路的方案数。递推伪代码如下：
(k 为枚举的中间点)

for m=1 to numEdge
for i=1 to n
for j=1 to n
for k=1 to n
if there's a direct path k->j
f[m][i][j] += f[m-1][i][k]

if 中的判断等价于: 矩阵 f[k][j] == 1，故 f[m-1][i][k] = f[m-1][i][k]*f[m-1][k][j]
可以发现这其实就是方阵自乘的变形形式
于是自乘 numEdge 次即可

• @ 2014-11-06 21:20:04

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 928 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 932 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 928 KiB, score = 10
测试数据 #3: Accepted, time = 93 ms, mem = 932 KiB, score = 10
测试数据 #4: Accepted, time = 140 ms, mem = 932 KiB, score = 10
测试数据 #5: Accepted, time = 187 ms, mem = 936 KiB, score = 10
测试数据 #6: Accepted, time = 140 ms, mem = 932 KiB, score = 10
测试数据 #7: Accepted, time = 187 ms, mem = 928 KiB, score = 10
测试数据 #8: Accepted, time = 156 ms, mem = 932 KiB, score = 10
测试数据 #9: Accepted, time = 156 ms, mem = 928 KiB, score = 10
Accepted, time = 1059 ms, mem = 936 KiB, score = 100
代码
type
arr=array[0..50,0..50] of int64;
var i,j,k,m,n,p,s,f:longint;
a,b:arr;{[0..60,0..60] of int64;}
function work(a,b:arr):arr;
var c:arr;
i,j,k,sum:longint;
begin
for i:=1 to n do
for j:=1 to n do
begin
sum:=0;
for k:=1 to n do
sum:=(sum+a[i,k]*b[k,j]) mod p;
c[i,j]:=sum mod p;
end;
exit(c);
end;
begin
for i:=1 to n do
for j:=1 to n do
for i:=1 to n do
for j:=1 to n do
b[i,j]:=a[i,j];
dec(m);
while m>0 do
begin
if m mod 2=1 then
a:=work(a,b);
b:=work(b,b);
m:=m div 2;
end;
writeln(a[s,f]);
end.

• @ 2013-10-28 18:37:03

没推导出来，试了试把输入的矩形自乘m次mod p，输出matrix[s,e]，结果ac

• @ 2009-10-28 09:43:04

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

• @ 2009-10-28 08:01:46

第一次递归

编译通过...

├ 测试数据 01：运行时错误...|错误号: 128

├ 测试数据 02：运行时错误...|错误号: 128

├ 测试数据 03：运行时错误...|错误号: 128

├ 测试数据 04：运行时错误...|错误号: 128

├ 测试数据 05：运行时错误...|错误号: 128

├ 测试数据 06：运行时错误...|错误号: 128

├ 测试数据 07：运行时错误...|错误号: 128

├ 测试数据 08：运行时错误...|错误号: 128

├ 测试数据 09：运行时错误...|错误号: 128

├ 测试数据 10：运行时错误...|错误号: 128

---|---|---|---|---|---|---|---|-

• @ 2009-10-06 10:36:10

居然是矩阵乘法。。太奇妙了

唉，我蒟蒻没想到。。

• @ 2009-10-02 14:58:37

假设a表示从i走到j要m步时的走法

mp为原邻接图

那么有

a := sgma(a*mp[k,j])(排列组合的乘法原理)

恰好和矩阵乘法

c := sgma(a*b[k,j])

一样

剩下的就是二分幂+矩阵乘法了

• @ 2009-10-01 15:47:07

程序提交时间

R1568472

Accepted

100

From jacklv－

P1603

FPC

Victoria Roo

2009-10-1 15:40:35

题目讲不清楚，但是交上去就ac了，怪哉！

矩阵乘法，一个矩阵的m次幂后一个元素a表示从i走到j长度为m的方案数

这样理解ac了，不知道对不

• @ 2009-09-21 10:02:21

MS

• @ 2009-08-28 18:58:33

果然。。

矩阵乘+快速幕=秒杀。。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

• @ 2009-08-15 00:14:16

果然要非递归，而且放matrix的数组刚好20，而且2^20刚好大于极限数据...

---|---|---|---|---|---|---|---|---|---|

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

• @ 2009-08-07 19:19:53

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 41ms

├ 测试数据 05：答案正确... 56ms

├ 测试数据 06：答案正确... 88ms

├ 测试数据 07：答案正确... 56ms

├ 测试数据 08：答案正确... 103ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：472ms

匆匆打完,居然如此之慢。。。

• @ 2009-08-07 15:06:11

快速幂+矩阵乘法，很快

• @ 2009-08-06 18:12:13

"

这题一下来就是50*50，堆个4层左右就会炸了

"

您该不会参数传数组吧？

• @ 2009-08-05 21:38:27

貌似c++比PASCAL快

• @ 2009-08-02 21:34:14

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 103ms

├ 测试数据 05：答案正确... 119ms

├ 测试数据 06：答案正确... 119ms

├ 测试数据 07：答案正确... 119ms

├ 测试数据 08：答案正确... 150ms

├ 测试数据 09：答案正确... 103ms

├ 测试数据 10：答案正确... 103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：816ms

第一次过 少于 20 人过的题...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

不用 int64 可以秒。

• @ 2009-08-01 18:35:45

裸矩阵乘啊！好……用来练习c++起步了……

• @ 2009-08-01 15:31:44

前面有题warden的闪烁序列。。程序基本没变。。就是把make_matrix给给成init_matrix，然后把power改成非递归而已。。

提醒下1067没爆栈这题爆栈的同志们。。那题是k的范围小，不断存储的matrix还在栈所能承受的范围之内，这题一下来就是50*50，堆个4层左右就会炸了。。so。。非递归王道。。

非递归的快速幂实际上就是二进制分解指数，有1的那位ans:=mul(ans,t,n,n,n)，然后不断t:=mul(t,t,n,n,n)直到指数分解完毕。。

我很弱。。讲的不是很清楚。。大家多尽量看吧。。

ID
1603

2

(无)

425

232

55%

1