首页 > ACM题库 > HDU-杭电 > hdu 2157 How many ways??-快速幂-[解题报告]C++
2013
12-30

hdu 2157 How many ways??-快速幂-[解题报告]C++

How many ways??

问题描述 :

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

输入:

输入数据有多组, 每组的第一行是2个整数 n, m(0 < n <= 20, m <= 100) 表示校园内共有n个点, 为了方便起见, 点从0到n-1编号,接着有m行, 每行有两个整数 s, t (0<=s,t<n) 表示从s点能到t点, 注意图是有向的.接着的一行是两个整数T,表示有T组询问(1<=T<=100),
接下来的T行, 每行有三个整数 A, B, k, 表示问你从A 点到 B点恰好经过k个点的方案数 (k < 20), 可以走重复边。如果不存在这样的走法, 则输出0
当n, m都为0的时候输入结束

输出:

输入数据有多组, 每组的第一行是2个整数 n, m(0 < n <= 20, m <= 100) 表示校园内共有n个点, 为了方便起见, 点从0到n-1编号,接着有m行, 每行有两个整数 s, t (0<=s,t<n) 表示从s点能到t点, 注意图是有向的.接着的一行是两个整数T,表示有T组询问(1<=T<=100),
接下来的T行, 每行有三个整数 A, B, k, 表示问你从A 点到 B点恰好经过k个点的方案数 (k < 20), 可以走重复边。如果不存在这样的走法, 则输出0
当n, m都为0的时候输入结束

样例输入:

4 4
0 1
0 2
1 3
2 3
2
0 3 2
0 3 3
3 6
0 1
1 0
0 2
2 0
1 2
2 1
2
1 2 1
0 1 3
0 0

样例输出:

2
0
1
3

#include <iostream>
#include <cstring>
#include <cstdio>
#define MAX 25
using namespace std;
struct matrix
{
    int num[MAX][MAX];
    matrix()
    {
        memset(num,0,sizeof(num));
    }
};
matrix res;
int n,m;
int map[MAX][MAX];
matrix A;
matrix operator*(matrix &a,matrix &b)
{
    matrix t;
    int i,j,k;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            t.num[i][j]=0;
            for(k=0;k<n;k++)
                t.num[i][j]+=(a.num[i][k]*b.num[k][j]);
            t.num[i][j]%=1000;
        }
    return t;
}
void quickpower(int x)
{
    while(x)
    {
        if(x&1)
            res=res*A;
        x>>=1;
        A=A*A;
    }
}
void init()
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            A.num[i][j]=map[i][j];
            res.num[i][j]=(i==j);
        }
    }
}
int main()
{

    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int i;
        if(n==0&&m==0)
            break;
        memset(map,0,sizeof(map));
        for(i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            map[u][v]=1;
        }
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int a,b,k;
            init();
            scanf("%d%d%d",&a,&b,&k);
            quickpower(k);
            printf("%d\n",res.num[a][b]%1000);
        }

    }
    return 0;
}

解题转自:http://blog.csdn.net/juststeps/article/details/8806449


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的