行列乗算の古典的な適用のパスの数
hdu 2157 How many ways？タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=2157
How many ways
Time Limit：2000/1000 MS（Java/Others） メモリLimit：32768/32768 K（Java/Others）Total Submission（s）：2098 Acceepted Submission(s)：769
Problem Description
春になりました。HDUキャンパスには花がいっぱい咲いています。色とりどりの花が咲き乱れています。とても綺麗です。玉葱は花を愛する人です。校花を見ていて、校草が咲き競っています。キャンパスを歩いています。気持ちもすっきりします。魅力的なキャンパスをたくさん見て、玉葱の頭で決めます。授業のたびに違った路線で教室に行きますが、時間の問題で毎回kの場所を通ります。今度のネギは2つのところを通ることにしました。彼はまず鼎広場に行って噴水を見て、教室に行ってもいいです。まず競技場に行って、何周か走ってから教室に行ってもいいです。彼はA時からちょうどk個の地点を通ってB時に到着する計画数を知りたいです。もちろんこの数はとても大きいかもしれません。だから、1000個の余りを出力すればいいです。彼を手伝ってもらえますか？ねぎの最初の日はどれぐらいの校花が見られるか決めましたよ。
Input
入力データは複数のグループがあり、各グループの1行目は2つの整数n、m(0<=n==20,m==100)はキャンパス内に合計n個の点があることを示しています。便宜上、点は0からn-1までで、次にm行があり、t(=0==s，t次のT行は、各行に3つの整数A、B、kがあります。A点からB点までちょうどk個の方案数（k<20）を通ります。重複して歩きます。このような歩き方が存在しない場合は、0を出力します。
n，mが全部0の場合、入力は終了します。
Output
毎回の問い合わせの方案数を計算します。歩き方が多いので、その対1000型の結果を出力します。
Sample Input
Sample Output
マトリックス乗算には、c.m[i][j]=c.m[i]+a.m[i]*b.m[j]と、図中のAからBまでの路線数を計算して連絡する重要なステップがあり、つまり、AからBは第三の間接点(中継局として)を経由して到達することができるので、数を蓄積する。そこで、図論はマトリクスと関連しています。
K=1,matrix[a][b]の値は結果【すなわち1または0】である。
K=2,matix[a][b]=matrix[a]+matrix[a]*matrix[k][b]は、中間にK点が一つ多くなりました。
K=3,aとbの間にK点を追加すると、3点（Bを含む）を経過するようになります。
これをもって類推する。
その結果、図の隣接マトリクスのK乗後A［a］［b］%modの値があります。
How many ways
Time Limit：2000/1000 MS（Java/Others） メモリLimit：32768/32768 K（Java/Others）Total Submission（s）：2098 Acceepted Submission(s)：769
Problem Description
春になりました。HDUキャンパスには花がいっぱい咲いています。色とりどりの花が咲き乱れています。とても綺麗です。玉葱は花を愛する人です。校花を見ていて、校草が咲き競っています。キャンパスを歩いています。気持ちもすっきりします。魅力的なキャンパスをたくさん見て、玉葱の頭で決めます。授業のたびに違った路線で教室に行きますが、時間の問題で毎回kの場所を通ります。今度のネギは2つのところを通ることにしました。彼はまず鼎広場に行って噴水を見て、教室に行ってもいいです。まず競技場に行って、何周か走ってから教室に行ってもいいです。彼はA時からちょうどk個の地点を通ってB時に到着する計画数を知りたいです。もちろんこの数はとても大きいかもしれません。だから、1000個の余りを出力すればいいです。彼を手伝ってもらえますか？ねぎの最初の日はどれぐらいの校花が見られるか決めましたよ。
Input
入力データは複数のグループがあり、各グループの1行目は2つの整数n、m(0<=n==20,m==100)はキャンパス内に合計n個の点があることを示しています。便宜上、点は0からn-1までで、次にm行があり、t(=0==s，t
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
マトリックス乗算には、c.m[i][j]=c.m[i]+a.m[i]*b.m[j]と、図中のAからBまでの路線数を計算して連絡する重要なステップがあり、つまり、AからBは第三の間接点(中継局として)を経由して到達することができるので、数を蓄積する。そこで、図論はマトリクスと関連しています。
K=1,matrix[a][b]の値は結果【すなわち1または0】である。
K=2,matix[a][b]=matrix[a]+matrix[a]*matrix[k][b]は、中間にK点が一つ多くなりました。
K=3,aとbの間にK点を追加すると、3点（Bを含む）を経過するようになります。
これをもって類推する。
その結果、図の隣接マトリクスのK乗後A［a］［b］%modの値があります。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mod=1e3;
int n,m;
struct matrix{
int m[21][21];
};
matrix A,I;
matrix multi(matrix a,matrix b){
matrix c;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
c.m[i][j]=0;
for(int k=0;k<n;k++){
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod;
}
}
}
return c;
}
matrix power(int k){
matrix ans=I,temp=A;
while(k){
if(k&1)ans=multi(ans,temp);
temp=multi(temp,temp);
k>>=1;
}
return ans;
}
int main()
{
//freopen("cin.txt","r",stdin);
for(int i=0;i<21;i++)I.m[i][i]=1;
while(cin>>n>>m&&(n+m)){
int a,b,k,t;
memset(A.m,0,sizeof(A.m));
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
A.m[a][b]=1;
}
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&a,&b,&k);
matrix res=power(k);
printf("%d
",res.m[a][b]);
}
}
return 0;
}