沼泽鳄鱼

ssl 2511

题目大意

给你一个无向图，有一些鳄鱼有周期性地在这个图中走（鳄鱼不用沿着边走，周期为2或3或4），问你从初始点走到最终点走k个单位时间，不在点和边上停下，不在同一时间和鳄鱼在同一点，有多少种走法

输入样例

6 8 1 5 3 0 2 2 1 1 0 0 5 5 1 1 4 4 3 3 5 1 3 0 5 1

输出样例

2

样例解释

时刻 -----------0 1 2 3
食人鱼位置 --0 5 1 0
路线一 --------1 2 0 5
路线二 --------1 4 3 5

数据范围

$1⩽N⩽50$
$1⩽K⩽2,000,000,000$
$1⩽NFish⩽20$

解题思路

可以拿2,3,4的最小公倍数12当成一个单位时间
然后预处理出12个时间的矩阵
然后快矩阵速幂
最后把余数处理一下即可

代码

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define wyc 10000 using namespace std; int n, m, t, x, y, st, ed, fn, s[100], v[100][100]; struct matrix {int n, m, a[60][60];matrix operator *(matrix const &b) const{matrix c;c.n = n;c.m = b.m;for (int i = 0; i < c.n; ++i)for (int j = 0; j < c.m; ++j)c.a[i][j] = 0;for (int i = 0; i < c.n; ++i)for (int k = 0; k < m; ++k)for (int j = 0; j < c.m; ++j)c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % wyc) % wyc;return c;} }A, B, C; matrix solve(matrix b, int x)//预处理 {matrix a;for (int i = 1; i <= x; ++i){matrix c = b;for (int j = 1; j <= fn; ++j)for (int k = 0; k < n; ++k)c.a[k][v[j][i % s[j]]] = 0;//有鳄鱼的地方直接清空if (i > 1) a = a * c;else a = c;}return a; } void Counting(int x) {while(x){if (x&1) A = A * B;B = B * B;x>>=1;}return; } int main() {scanf("%d%d%d%d%d", &n, &m, &st, &ed, &t);C.n = C.m = A.m = n;A.n = 1;A.a[0][st] = 1;for (int i = 1; i <= m; ++i){scanf("%d%d", &x, &y);C.a[x][y] = 1;C.a[y][x] = 1;}scanf("%d", &fn);for (int i = 1; i <= fn; ++i){scanf("%d", &s[i]);for (int j = 0; j < s[i]; ++j)scanf("%d", &v[i][j]);}B = solve(C, 12);Counting(t / 12);if (t % 12) A = A * solve(C, t % 12);//解决余数printf("%d", A.a[0][ed]);return 0; }

总结

以上是生活随笔为你收集整理的【矩阵乘法】沼泽鳄鱼（ssl 2511）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。