HDU 2157 How many ways??

题目在这里>_<

题意

春天到了, HDU校园里开满了花, 姹紫嫣红, 非常美丽. 葱头是个爱花的人, 看着校花校草竞相开放, 漫步校园, 心情也变得舒畅. 为了多看看这迷人的校园, 葱头决定, 每次上课都走不同的路线去教室, 但是由于时间问题, 每次只能经过 $k$ 个地方, 比方说, 这次葱头决定经过 $2$ 个地方, 那他可以先去问鼎广场看看喷泉, 再去教室, 也可以先到体育场跑几圈, 再到教室. 他非常想知道, 从 $A$ 点恰好经过 $k$ 个点到达 $B$ 点的方案数, 当然这个数有可能非常大, 所以你只要输出它模上 $1000$ 的余数就可以了. 你能帮帮他么?? 你可决定了葱头一天能看多少校花哦。

思路

建立关系矩阵$i$能到达$j$则$a_{ij}=1$否则$a_{ij}=0$.那么$A^n$即为每个点恰好经过$n$个点相互到达的方案数。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
//#define test
using namespace std;
const int Nmax=200;
typedef long long ll;
const int mod=1000;
struct Matrix
{
    int n,m;
    int map[Nmax][Nmax];
    Matrix(int x,int y)
    {
        n=x;m=y;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                map[i][j]=0;
    }
    Matrix operator * (const Matrix b)
    {
        Matrix c(n,b.m);
        if(m==b.n)
        {
            for(int i=1;i<=c.n;i++)
                for(int k=1;k<=m;k++)
                    for(int j=1;j<=c.m;j++)
                        c.map[i][j]=(c.map[i][j]+(map[i][k]*b.map[k][j])%mod)%mod;
            return c;
        }
        printf("error!!!!!!!!!!!!!!\n");   
        return c;
    }
    void show()
    {
        printf("n:%d m:%d\n",n,m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                printf("%4d%c",map[i][j],j==m?'\n':' ');
    }
};
int a,b,n,k,m;
int mp[Nmax][Nmax];
int work()
{
    Matrix base(n,n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            base.map[i][j]=mp[i][j];
    //base.show();
    //if(k==0)
        //return base.map[a][b];
    Matrix ans(n,n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j)
                ans.map[i][j]=1;
    while(k)
    {
        if(k&1)
            ans=ans*base;
        base=base*base;
        k>>=1;
    }
    //ans.show();
    //now.show();
    return ans.map[a][b];
}
int main()
{
    #ifdef test
    #endif
    //freopen("f.in","r",stdin);
    int s,t;
    while(~scanf("%d%d",&n,&m))
    {
        if(!n && !m)
            break;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                mp[i][j]=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&s,&t);
            mp[s+1][t+1]=1;
        }
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d%d",&a,&b,&k);
            a++,b++;
            printf("%d\n",work());
        }
    }
    return 0;
}