hdu2157 How many ways??
3859 ワード
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2181 Accepted Submission(s): 816
Problem Description
春になって、HDUキャンパスの中で花がいっぱい咲いて、色とりどりで美しくて、とても美しいです.ネギの頭は花が好きな人で、学校の花を見て学校の草が咲き乱れているのを見て、キャンパスを歩いて、気持ちも楽になりました.この魅力的なキャンパスをもっと見るために、ネギの頭は決めて、授業のたびに異なるルートを歩いて教室に行きますが、時間の問題のため、毎回kつの場所を通るしかありません.例えば、今度のネギの头は2つの地方を通ることを决めて、それでは彼は先に鼎広场に行って喷水を见て、更に教室に行って、先にスタジアムまで何周走って、更に教室に着きます.ネギの頭が一日にどれだけの校花を見ることができるか決めましたよ.
Input
入力データは複数組あり、各組の1行目は2個の整数n、m(0次のT行は、各行に3つの整数A,B,kがあり、A点からB点までちょうどk点を通過するシナリオ数(k<20)を聞いて、繰り返しエッジを歩くことができます.このような歩き方が存在しなければ0を出力する
n,mがいずれも0の場合に入力が終了する
Output
質問ごとのシナリオ数を計算すると,歩き方が多いため,1000に対して型を取った結果を出力する.
Sample Input
Sample Output
この問題は行列の高速べき乗で行うことができ,まず行列を隣接行列で表すことができ,i,jの間に道があればa[i][j]は1であり,そうでなければ0である.では,2つのaを乗算してc,c[i][j]=Σa(i,k)*a(k,j)は、iからある場所kを通ってjまで行くことであり、a^kはiからkを通ってjまで行くルートの本数である.
Problem Description
春になって、HDUキャンパスの中で花がいっぱい咲いて、色とりどりで美しくて、とても美しいです.ネギの頭は花が好きな人で、学校の花を見て学校の草が咲き乱れているのを見て、キャンパスを歩いて、気持ちも楽になりました.この魅力的なキャンパスをもっと見るために、ネギの頭は決めて、授業のたびに異なるルートを歩いて教室に行きますが、時間の問題のため、毎回kつの場所を通るしかありません.例えば、今度のネギの头は2つの地方を通ることを决めて、それでは彼は先に鼎広场に行って喷水を见て、更に教室に行って、先にスタジアムまで何周走って、更に教室に着きます.ネギの頭が一日にどれだけの校花を見ることができるか決めましたよ.
Input
入力データは複数組あり、各組の1行目は2個の整数n、m(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
この問題は行列の高速べき乗で行うことができ,まず行列を隣接行列で表すことができ,i,jの間に道があればa[i][j]は1であり,そうでなければ0である.では,2つのaを乗算してc,c[i][j]=Σa(i,k)*a(k,j)は、iからある場所kを通ってjまで行くことであり、a^kはiからkを通ってjまで行くルートの本数である.
#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
#define inf 99999999
#define pi acos(-1.0)
#define MOD 1000
int gra[25][25];
struct matrix{
ll n,m,i;
ll data[99][99];
void init_danwei(){
for(i=0;i<n;i++){
data[i][i]=1;
}
}
};
matrix multi(matrix &a,matrix &b){
ll i,j,k;
matrix temp;
temp.n=a.n;
temp.m=b.m;
for(i=0;i<temp.n;i++){
for(j=0;j<temp.m;j++){
temp.data[i][j]=0;
}
}
for(i=0;i<a.n;i++){
for(k=0;k<a.m;k++){
if(a.data[i][k]>0){
for(j=0;j<b.m;j++){
temp.data[i][j]=(temp.data[i][j]+(a.data[i][k]*b.data[k][j])%MOD )%MOD;
}
}
}
}
return temp;
}
matrix fast_mod(matrix &a,ll n){
matrix ans;
ans.n=a.n;
ans.m=a.m;
memset(ans.data,0,sizeof(ans.data));
ans.init_danwei();
while(n>0){
if(n&1)ans=multi(ans,a);
a=multi(a,a);
n>>=1;
}
return ans;
}
int main()
{
ll n,m,i,j,c,d,k,T;
while(scanf("%lld%lld",&n,&m)!=EOF)
{
if(n==0 && m==0)break;
matrix a;
memset(a.data,0,sizeof(a.data));
a.n=a.m=n;
for(i=1;i<=m;i++){
scanf("%lld%lld",&c,&d);
a.data[c][d]=1;
}
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld%lld",&c,&d,&k);
matrix b;
memset(b.data,0,sizeof(b.data));
b.n=b.m=n;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
b.data[i][j]=a.data[i][j];
}
}
matrix ans;
ans=fast_mod(b,k);
printf("%lld
",ans.data[c][d]%MOD);
}
}
return 0;
}