首页 > 代码库 > hdu 2157 How many ways?? (矩阵快速幂)
hdu 2157 How many ways?? (矩阵快速幂)
题目大意:
问A-B 走K 部的方法数。
如果矩阵 a 为任意一个点到另外一个点 走 1 步的方法数
那么 a*a 就是任意一个点到另外一个点 走 2 步的方法数
。。。
那么直接快速幂。
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #define N 10 using namespace std; int mod = 1000; typedef long long LL; struct matrix { int a[20][20]; }origin; int n,m; matrix multiply(matrix x,matrix y) { matrix temp; memset(temp.a,0,sizeof(temp.a)); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { for(int k=0;k<n;k++) { temp.a[i][j]+=x.a[i][k]*y.a[k][j]; temp.a[i][j]=(temp.a[i][j])%mod; } } } return temp; } matrix matmod(matrix A,int k) { matrix res; memset(res.a,0,sizeof res.a); for(int i=0;i<n;i++)res.a[i][i]=1; while(k) { if(k&1) res=multiply(res,A); k>>=1; A=multiply(A,A); } return res; } void print(matrix x) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) cout<<" "<<x.a[i][j]; puts(""); } printf("---------------\n"); } int main() { while(scanf("%d%d",&n,&m)!=EOF) { if(n==0 && m==0)break; memset(origin.a,0,sizeof origin.a); while(m--) { int s,e; scanf("%d%d",&s,&e); origin.a[s][e]=1; } int Q; scanf("%d",&Q); while(Q--) { int s,e,k; scanf("%d%d%d",&s,&e,&k); matrix res = matmod(origin,k); printf("%d\n",res.a[s][e]); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。