题意 : 给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值
从这道题才知道邻接矩阵竟然可以乘 , 惊了 ! ! ! 矩阵真的不是白叫的 .
虽然很容易推出是可行的但是还是觉得很神奇 .
WA了几百次 , 后来发现是快速幂的问题 , 我还是不知道为什么 ,
我之前的快速幂因为不想初始化z都直接在第一次乘的时候特殊判断直接把x赋给z , 也没有出现问题 , 但是既然错了...就这样写吧 , 记住就好了 .
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 const int maxn=110; 9 const double eps=1e-8; 10 const long long modn=1000; 11 int n,m; 12 struct mat{ 13 int e[31][31]; 14 mat(){ 15 memset(e,0,sizeof(e)); 16 } 17 }; 18 mat pro(mat x,mat y){ 19 mat z; 20 for(int i=1;i<=n;i++){ 21 for(int j=1;j<=n;j++){ 22 for(int k=1;k<=n;k++){ 23 z.e[i][j]+=x.e[i][k]*y.e[k][j]; 24 z.e[i][j]%=1000; 25 } 26 } 27 }return z; 28 } 29 mat pow(mat x,int k){ 30 mat z; 31 for(int i=1;i<=n;i++){ 32 z.e[i][i]=1; 33 } 34 while(k){ 35 if(k%2==1){ 36 z=pro(z,x); 37 } 38 x=pro(x,x); 39 k/=2; 40 } 41 return z; 42 } 43 int main(){ 44 while(~scanf("%d%d",&n,&m)&&(m||n)){ 45 mat a; 46 mat c; 47 int x,y,k; 48 for(int i=1;i<=m;i++){ 49 scanf("%d%d",&x,&y); 50 a.e[x+1][y+1]=1; 51 } 52 scanf("%d",&m); 53 for(int i=1;i<=m;i++){ 54 scanf("%d%d%d",&x,&y,&k); 55 c=a; 56 c=pow(a,k); 57 int ans=c.e[x+1][y+1]%1000; 58 printf("%d ",ans); 59 } 60 } 61 return 0; 62 }