题解 - Vijos

1

2585479524 LV 7 @ 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;
    }
        
}

1

lixuanjing LV 9 @ 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;
}

-1

wang_yanheng LV 10 @ 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 次即可

-1

零度微凉 LV 8 @ 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
readln(n);
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
for i:=1 to n do
for j:=1 to n do
b[i,j]:=a[i,j];
readln(m,s,f,p);
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.

-1

Zggh LV 10 @ 2013-10-28 18:37:03

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

-1

yzl609271536 LV 10 @ 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

-1

陈亮宇 LV 10 @ 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

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

-1

181818181818 LV 10 @ 2009-10-06 10:36:10

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

唉，我蒟蒻没想到。。

-1

木子日匀 LV 10 @ 2009-10-02 14:58:37

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

mp为原邻接图

那么有

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

恰好和矩阵乘法

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

一样

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

-1

jacklv LV 10 @ 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了，不知道对不

-1

SDreaming LV 10 @ 2009-09-21 10:02:21

MS

-1

lgxcgd LV 10 @ 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

-1

527971925 LV 10 @ 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

-1

boyzkk LV 10 @ 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

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

-1

Holy_one LV 8 @ 2009-08-07 15:06:11

快速幂+矩阵乘法，很快

-1

hahacool LV 10 @ 2009-08-06 18:12:13

"

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

"

您该不会参数传数组吧？

-1

esan1234567 LV 10 @ 2009-08-05 21:38:27

貌似c++比PASCAL快

-1

Matt LV 10 @ 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 可以秒。

-1

fammiebright LV 9 @ 2009-08-01 18:35:45

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

-1

fenghao LV 10 @ 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)直到指数分解完毕。。

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

题解

26 条题解

迷宫

信息

状态

开发

支持

题解

26 条题解

迷宫

信息

状态

开发

支持

还没有账户？

登录