[BZOJ1898] Swamp 沼泽鳄鱼 矩阵快速幂

本文主要是介绍[BZOJ1898] Swamp 沼泽鳄鱼 矩阵快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

可以发现鱼的周期 T = 2， 3， 4；

lcm (2， 3， 4) = 12；

所以当前时刻可以通行的邻接矩阵以12为周期出现

预处理出12个矩阵G[12] 然后全部乘起来存入Tmp

最后答案矩阵为 (Tmp^12) * G1 * ... * Gk%12 

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN 50
#define MAXM 50
#define MAXF 20
typedef int LL;
struct Maxtrix{  int n, m;  LL A[MAXN+10][MAXN+10];  
}E, Z;
int n, m, ST, ED, K, Fish;
const int p = 10000;
int way[MAXF][5];
Maxtrix Map, G[12], Tmp;
void init(Maxtrix &X)
{X.n = X.m = 0;memset(X.A, 0, sizeof(X.A));
}
void Get_E()
{E.n = E.m = MAXN;for(int i = 0; i < E.n; i++) E.A[i][i] = 1;
}
Maxtrix add(Maxtrix AA, Maxtrix BB)
{Maxtrix D; D = AA;for(int i = 0; i < AA.n; i++)for(int j = 0; j < AA.m; j++){D.A[i][j] += BB.A[i][j];D.A[i][j] %= p;}return D;
}
Maxtrix mul(Maxtrix AA, Maxtrix BB)
{Maxtrix D;init(D);D.n = AA.n;D.m = BB.m;for(int i = 0; i < AA.n; i++)for(int j = 0; j < BB.n; j++)for(int k = 0; k < BB.m; k++){D.A[i][k] += (AA.A[i][j] * BB.A[j][k]) % p;D.A[i][k] %= p;}return D;
}
Maxtrix pow_mod(Maxtrix &A, int k)
{Maxtrix ans = E, t = A;ans.n = A.n;ans.m = A.m;while(k){if(k & 1)ans = mul(ans, t);t = mul(t, t);k >>= 1;}return ans;
}
void Build()
{for(int tim = 0; tim < 12; tim++){G[tim] = Map;for(int f = 0; f < Fish; f++){int u = way[f][tim % way[f][4]];for(int v = 0; v < n; v++) {if(tim) G[tim-1].A[v][u] = 0;G[tim].A[u][v] = 0;}}}
}
int main()
{Get_E();scanf("%d%d%d%d%d", &n, &m, &ST, &ED, &K);Map.n = Map.m = E.m = E.n = n;Tmp = E;for(int i = 1; i <= m; i++){int u, v;scanf("%d%d", &u, &v);Map.A[u][v] = Map.A[v][u] = 1;}scanf("%d", &Fish);for(int i = 0; i < Fish; i++){scanf("%d", &way[i][4]);for(int j = 0; j < way[i][4]; j++) scanf("%d", &way[i][j]);}Build();for(int i = 0; i < 12; i++) Tmp = mul(Tmp, G[i]);Tmp = pow_mod(Tmp, K / 12);K %= 12;for(int i = 0; i < K; i++) Tmp = mul(Tmp, G[i]);printf("%d", Tmp.A[ST][ED]);
}

这篇关于[BZOJ1898] Swamp 沼泽鳄鱼 矩阵快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---