比赛 |
2024暑假C班集训D |
评测结果 |
AAAAAAAAAA |
题目名称 |
沼泽鳄鱼 |
最终得分 |
100 |
用户昵称 |
darkMoon |
运行时间 |
0.263 s |
代码语言 |
C++ |
内存使用 |
4.16 MiB |
提交时间 |
2024-07-13 09:55:02 |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
// #define fin cin
// #define fout cout
ifstream fin("swamp.in");
ofstream fout("swamp.out");
auto mread = [](){
int x;
fin >> x;
return x;
};
const int N = 55, MOD = 10000;
int n = mread(), m = mread(), s = mread() + 1, t = mread() + 1, k = mread(), a[N][N], nf, b[N][N];
struct node{
int a[N][N];
node(){
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
a[i][j] = 0;
}
}
}
friend node operator * (node a, node b){
node ans;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
for(int k = 1; k <= n; k ++){
(ans.a[i][j] += a.a[i][k] * b.a[k][j] % MOD) %= MOD;
}
}
}
return ans;
}
};
node ksm(node x, int k){
node now = x, ans;
for(int i = 1; i <= n; i ++){
ans.a[i][i] = 1;
}
while(k){
if(k & 1){
ans = ans * now;
}
now = now * now;
k >>= 1;
}
return ans;
}
signed main(){
for(int i = 1, x, y; i <= m; i ++){
x = mread() + 1, y = mread() + 1;
a[x][y] ++;
a[y][x] ++;
}
nf = mread();
for(int i = 1; i <= nf; i ++){
b[i][0] = mread();
for(int j = 1; j <= b[i][0]; j ++){
b[i][j] = mread() + 1;
}
for(int j = 1; j <= 12; j ++){
int tmp = (j - 1) % b[i][0] + 1;
b[i][j] = b[i][tmp];
}
}
node c[20];
for(int i = 1; i <= 11; i ++){
for(int j = 1; j <= n; j ++){
for(int k = 1; k <= n; k ++){
int e = 1;
for(int l = 1; l <= nf; l ++){
if(k == b[l][i + 1]){
e = 0;
break;
}
}
if(e){
c[i].a[j][k] = a[j][k];
}
}
}
// printf("--- %lld\n", i);
// for(int j = 1; j <= n; j ++){
// for(int k = 1; k <= n; k ++){
// printf("%lld ", c[i].a[j][k]);
// }
// printf("\n");
// }
}
for(int j = 1; j <= n; j ++){
for(int k = 1; k <= n; k ++){
int e = 1;
for(int l = 1; l <= nf; l ++){
if(k == b[l][1]){
e = 0;
break;
}
}
if(e){
c[12].a[j][k] = a[j][k];
}
}
}
node tmp = c[1];
for(int i = 2; i <= 12; i ++){
tmp = tmp * c[i];
}
node ans = ksm(tmp, k / 12);
for(int i = 1; i <= k % 12; i ++){
ans = ans * c[i];
// printf("*** %lld\n", i);
// for(int j = 1; j <= n; j ++){
// for(int k = 1; k <= n; k ++){
// printf("%lld ", ans.a[j][k]);
// }
// printf("\n");
// }
}
fout << ans.a[s][t];
return 0;
}