#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<string.h>
#define LL long long
#define mod 1000
using namespace std;
struct mat
{
int m[105][105];
}unit;
int n,m;
void init_unit()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j)
{
unit.m[i][j] = 1;
}
}
}
}
mat operator * (mat a, mat b)
{
mat ret;
LL x;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
x = 0;
for(int k=0;k<n;k++)
{
x += ((LL)a.m[i][k] * b.m[k][j])%mod;
ret.m[i][j] = x%mod;
}
}
}
return ret;
}
mat pow_mat(mat a, LL x)
{
mat ret = unit;
while(x)
{
if(x & 1) ret = ret*a;
a = a*a;
x >>= 1;
}
return ret;
}
void print(mat tmp)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
printf("%d ",tmp.m[i][j]);
}
printf("\n");
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==0&m==0) break;
init_unit();
mat am;
memset(am.m,0,sizeof(am.m));
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
am.m[a][b] = 1;
}
//print(am);
int t;
scanf("%d",&t);
for(int i=0;i<t;i++)
{
int a,b,k;
scanf("%d%d%d",&a,&b,&k);
mat tmp = pow_mat(am,k);
//print(tmp);
printf("%d\n",tmp.m[a][b]);
}
}
}
矩阵快速幂的模板
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 这样才能使对矩阵快速幂有深入的理解!!!(其余基础的不懂就请看我另一篇简书!!!)代码如下:
- Xamarin XAML语言教程构建ControlTemplate控件模板 控件模板ControlTemplate...
