矩阵十大经典题目之八 how many ways

开始学矩阵，借鉴了一些网上的文章，渐渐地去领会。这是第一题。加油！

题目大意：给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值

把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。

就是转化为矩阵，然后算矩阵的乘法。

#include<cstdio>
#include<iostream>
#include<cstring>
#define mol 1000007
#define rep(i,j,k) for(int i = j; i <= k; i++)
using namespace std;

int m, n;

struct maxtrix{
    int mat[32][32];
    maxtrix(){
        memset(mat,0,sizeof(mat));
    }
};

int read()
{
    int s = 0, t = 1;
    char c = getchar();
    while( !isdigit(c) ){
        if( c == '-' ) t = -1;
        c = getchar();
    }
    while( isdigit(c) ){
        s = s * 10 + c - '0';
        c = getchar();
    }
    return s * t;
}

maxtrix pow_mul(maxtrix x, maxtrix y)
{
    maxtrix z;
    rep(i,1,m){
        rep(j,1,m){
            rep(k,1,m){
              z.mat[i][j] = ( z.mat[i][j] + x.mat[i][k] * y.mat[k][j] )% mol;
            }
        }
    }
    return z;
}

maxtrix powl(maxtrix a,int k)
{
    maxtrix b;
    rep(i,1,m) b.mat[i][i] = 1;
    while( k ){
        if( k & 1 ) b = pow_mul(b,a);
        a = pow_mul(a,a);
        k >>= 1;
    }
    return b;
}

int main()
{
    m = read();
    n = read();
    maxtrix a;
    rep(i,1,n){
        int x = read(), y = read();
        a.mat[x][y] = 1;
    }
    int t = read();
    while( t-- ){
        int x = read(), y = read(), k = read();
        maxtrix b;
        b = powl(a,k);
        cout<<b.mat[x][y]<<endl;
    }
    return 0;
}

矩阵十大经典题目之八 how many ways

相关推荐