How many ways?? - hdu2157(矩阵快速幂-模板)

分析:求Map^k,刚开始没有用快速幂,TLE了

 
代码如下:
====================================================================================================
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std; const int MAXN = ;
const int mod = ; struct Matrix
{///定义一个矩阵
int edge[MAXN][MAXN];
}; int N; void Mul(Matrix a, Matrix b, Matrix &ans)
{///a * b -> ans
memset(ans.edge, , sizeof(ans.edge)); for(int i=; i<N; i++)
for(int j=; j<N; j++)
for(int p=; p<N; p++)
{
ans.edge[i][j] += a.edge[i][p] * b.edge[p][j];
ans.edge[i][j] %= mod;
}
}
void QuickPow(Matrix Map, int k, Matrix &ans)
{///Map^k -> ans
memset(ans.edge, , sizeof(ans.edge)); for(int i=; i<N; i++)
ans.edge[i][i] = true; while(k)
{
if(k & )
Mul(ans, Map, ans);
Mul(Map, Map, Map); k /= ;
}
} int main()
{
int M; while(scanf("%d%d", &N, &M), M+N)
{
int u, v, k;
Matrix Map, ans; memset(Map.edge, , sizeof(Map.edge)); while(M--)
{
scanf("%d%d", &u, &v);
Map.edge[u][v] = true;
} scanf("%d", &M); while(M--)
{
scanf("%d%d%d", &u, &v, &k); QuickPow(Map, k, ans); printf("%d\n", ans.edge[u][v]);
}
} return ;
}
上一篇:What and where are the stack and heap?


下一篇:sql openxml sp_xml_preparedocument xml 中文乱码