开网站 主机 服务器,外贸型网站开发,教育培训网站大全,红铃铛网站建设沼泽鳄鱼
ssl 2511
题目大意
给你一个无向图#xff0c;有一些鳄鱼有周期性地在这个图中走#xff08;鳄鱼不用沿着边走#xff0c;周期为2或3或4#xff09;#xff0c;问你从初始点走到最终点走k个单位时间#xff0c;不在点和边上停下#xff0c;不在同一时间和鳄…沼泽鳄鱼
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⩽501 \leqslant N \leqslant 501⩽N⩽50 1⩽K⩽2,000,000,0001 \leqslant K \leqslant 2,000,000,0001⩽K⩽2,000,000,000 1⩽NFish⩽201 \leqslant NFish \leqslant 201⩽NFish⩽20
解题思路
可以拿2,3,4的最小公倍数12当成一个单位时间 然后预处理出12个时间的矩阵 然后快矩阵速幂 最后把余数处理一下即可
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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 (x1) A A * B;B B * B;x1;}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;
}
