hdoj 2157 How many ways?? [매트릭스 쾌속 멱] [임의의 두 점 간 의 경로 에서 k 개 점 을 통과 하 는 방안 수 를 구하 십시오]

How many ways?? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2102    Accepted Submission(s): 771
Problem Description
봄 이 되자 HDU 캠퍼스 에 꽃 이 가득 피 었 습 니 다. 여러 종류의 아름 다운 꽃 들 이 아름 답 습 니 다. 파 는 꽃 을 사랑 하 는 사람 입 니 다. 학교 화초 가 경쟁 적 으로 열 리 는 것 을 보고 캠퍼스 를 거 닐 면 마음 도 편안 해 집 니 다. 이 아름 다운 캠퍼스 를 많이 보기 위해 파 는 수업 할 때마다 다른 노선 으로 교실 에 가기 로 결 정 했 습 니 다. 그러나 시간 문제 로 매번 k 곳 만 지나 갈 수 있 습 니 다. 예 를 들 어...이번에 파 머리 는 두 곳 을 지나 기로 했 습 니 다. 그러면 그 는 먼저 정 광장 에 가서 분 수 를 보고 교실 에 갈 수도 있 습 니 다. 먼저 운동장 에 가서 몇 바퀴 뛰 고 교실 에 갈 수도 있 습 니 다. 그 는 A 시 에 마침 k 시 를 거 쳐 B 시 에 도착 하 는 방안 을 알 고 싶 어 합 니 다. 물론 이 숫자 는 매우 클 수 있 습 니 다. 그래서 1000 의 나머지 를 출력 하면 됩 니 다. 당신 이 그 를 도와 줄 수 있 습 니까?너 는 파 를 하루 에 얼마나 볼 수 있 는 지 결정 했다.
 
Input
입력 데 이 터 는 여러 그룹 이 있 습 니 다. 각 그룹의 첫 번 째 줄 은 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 일 때 입력 이 끝 납 니 다.
 
Output
매번 물 어 보 는 방안 수 를 계산 합 니 다. 방법 이 많 기 때문에 1000 모델 에 대한 결 과 를 출력 합 니 다.
 
Sample Input

       
       
       
       

        
        
        
        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
       
       
       
       

 
Sample Output

       
       
       
       

        
        
        
        2
0
1
3
       
       
       
       

 
이산 수 학파 가 쓸모 가 있 게 되 었 다.
주의: 제목 에서 말 한 k 점 은 종점 을 포함한다.
사고방식: 도 론 과 행렬 을 연결시킨다.i 점 에서 j 점 까지 경로 가 있 으 면 행렬 의 i 행 j 열 에 있 는 요 소 는 1 이 고 반대로 0 이다.
그림 은 행렬 A 로 표시 한 후에 이러한 성질 이 있다. i 점 에서 j 점 까지 1 개의 중간 점 의 변 을 거 쳐 중복 할 수 있 는 경로 수 는ΣA (i, k) * A (k, j), 그 중에서 k 는 중간 점 입 니 다.우리 가 구 해 야 할 것 은 s 점 에서 t 점 까지 k 점 (k - 1 개의 중간 점 을 거 쳐) 의 변 에서 중복 가능 한 경로 수 입 니 다.따라서 우 리 는 행렬 A 의 K 차 멱 만 필요 하 다. 마지막 행렬 A (s, t) 위치의 요 소 는 바로 답 이다.
AC 코드:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 20+10
#define LL long long
#define MOD 1000
using namespace std;
struct Matrix
{
    int a[MAXN][MAXN];
    int r, c;
};
Matrix ori, res;
int s[110], t[110];
void init(int n, int m)
{
    ori.r = ori.c = res.r = res.c = n;
    memset(ori.a, 0, sizeof(ori.a));
    memset(res.a, 0, sizeof(res.a));
    for(int i = 0; i < n; i++)//      
        res.a[i][i] = 1;
    for(int i = 0; i < m; i++)
        ori.a[s[i]][t[i]] = 1;
}
Matrix muitl(Matrix x, Matrix y)
{
    Matrix z;
    memset(z.a, 0, sizeof(z.a));
    z.r = x.r; z.c = y.c;
    for(int i = 0; i < x.r; i++)
    {
        for(int k = 0; k < x.c; k++)
        {
            if(x.a[i][k] == 0) continue;
            for(int j = 0; j < y.c; j++)
                z.a[i][j] = (z.a[i][j] + (x.a[i][k] * y.a[k][j]) % MOD) % MOD;
        }
    }
    return z;
}
void Matrix(int s, int t, int n)
{
    while(n)
    {
        if(n & 1)
            res = muitl(ori, res);
        ori = muitl(ori, ori);
        n >>= 1;
    }
    printf("%d
", res.a[s][t]);//     
}
int main()
{
    int N, M, Q;
    while(scanf("%d%d", &N, &M), N||M)
    {
        for(int i = 0; i < M; i++)
            scanf("%d%d", &s[i], &t[i]);
        scanf("%d", &Q);
        int A, B, K;
        while(Q--)
        {
            scanf("%d%d%d", &A, &B, &K);
            init(N, M);//          
            Matrix(A, B, K);//    K  
        }
    }
    return 0;
}