hdu 2157 How many ways? (矩阵高速幂)

hdu 2157 How many ways?? (矩阵快速幂)

题目大意：

问A-B 走K 部的方法数。

如果矩阵 a 为任意一个点到另外一个点 走 1 步的方法数

那么 a*a 就是任意一个点到另外一个点 走 2 步的方法数

。。。

那么直接快速幂。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define N 10

using namespace std;
int mod = 1000;
typedef long long LL;

struct matrix
{
    int a[20][20];
}origin;


int n,m;

matrix multiply(matrix x,matrix y)
{
    matrix temp;
    memset(temp.a,0,sizeof(temp.a));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            for(int k=0;k<n;k++)
            {
                temp.a[i][j]+=x.a[i][k]*y.a[k][j];
                temp.a[i][j]=(temp.a[i][j])%mod;
            }
        }
    }
    return temp;
}

matrix matmod(matrix A,int k)
{
    matrix res;

    memset(res.a,0,sizeof res.a);
    for(int i=0;i<n;i++)res.a[i][i]=1;

    while(k)
    {
        if(k&1)
        res=multiply(res,A);
        k>>=1;
        A=multiply(A,A);
    }
    return res;
}

void print(matrix x)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        cout<<" "<<x.a[i][j];
        puts("");
    }
    printf("---------------\n");
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0 && m==0)break;

        memset(origin.a,0,sizeof origin.a);

        while(m--)
        {
            int s,e;
            scanf("%d%d",&s,&e);
            origin.a[s][e]=1;
        }

        int Q;
        scanf("%d",&Q);

        while(Q--)
        {
            int s,e,k;
            scanf("%d%d%d",&s,&e,&k);
            matrix res = matmod(origin,k);
            printf("%d\n",res.a[s][e]);
        }
    }
    return 0;
}