HDU 2157 How many ways??
离散数学中证明过这样一个结论:
书上写了一大堆,说人话 就是:
从u点到v点恰好经过k步的方案数,为邻接矩阵的k次幂得到的矩阵(假设是ans)中的元素ans[u][v]。
出题人比较友好,幂次比较小(k<20),不用矩阵快速幂也能过,但还是写一下矩阵快速幂的代码:
#include <bits/stdc++.h>
using namespace std;
const int N=22,mod=1000;
int n,m,x,y,k,q;
struct node
{
int m[N][N];
}s;
node mul(node s1,node s2) // 两矩阵相乘
{
node ans;
memset(ans.m,0,sizeof(ans.m));
// 全部初始化为0(结构体内不会自动初始化)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
ans.m[i][j]=(ans.m[i][j]+s1.m[i][k]*s2.m[k][j]%mod)%mod;
return ans;
}
node qpow(node a,int b) // 矩阵a的b次幂
{
node ans;
memset(ans.m,0,sizeof(ans.m));
for(int i=0;i<n;i++)
ans.m[i][i]=1; // ans初始化为单位矩阵
while(b)
{
if(b&1)ans=mul(ans,a);
a=mul(a,a);
b/=2;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>n>>m&&(n||m))
{
memset(s.m,0,sizeof(s.m));
for(int i=1;i<=m;i++)
{
cin>>x>>y;
s.m[x][y]=1; // 如果有重边也只算一条路
}
cin>>q;
node ans;
while(q--)
{
cin>>x>>y>>k;
ans=qpow(s,k);
printf("%d\n",ans.m[x][y]);
}
}
return 0;
}