记录编号	601053	评测结果	AAAAAAAAAA
题目名称	1469.[ZJOI 2005] 沼泽鳄鱼	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	0.159 s
提交时间	2025-05-27 22:26:26	内存使用	1.83 MiB

#include <cstdio>
#include <cstring>

constexpr int MAXN = 50;
constexpr int MOD = 10000;

struct Matrix {
  int n, m;
  int a[MAXN][MAXN];
  Matrix() {
    memset(a, 0, sizeof a);
  }
  Matrix(int n, int m) : n(n), m(m) {
    memset(a, 0, sizeof a);
  }
  void E() {
    memset(a, 0, sizeof a);
    for (int i = 0; i < n; ++i) {
      a[i][i] = 1;
    }
  }
  int* operator[] (int val) {
    return a[val];
  }
};

Matrix operator * (Matrix x, Matrix y) {
  Matrix res(x.n, y.m);
  for (int k = 0; k < x.m; ++k) {
    for (int i = 0; i < x.n; ++i) {
      for (int j = 0; j < y.m; ++j) {
        res[i][j] = (res[i][j] + x[i][k] * y[k][j] + MOD) % MOD;
      }
    }
  }
  return res;
}

Matrix kasumi(Matrix a, int b) {
  Matrix res = a;
  res.E();
  while (b) {
    if (b & 1) res = res * a;
    b >>= 1;
    a = a * a;
  }
  return res;
}

int n, m, st, ed, k;
int nfish;

int main() {
  freopen("swamp.in", "r", stdin);
  freopen("swamp.out", "w", stdout);
  scanf("%d %d %d %d %d", &n, &m, &st, &ed, &k);

  Matrix g(n, n);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    g[x][y] = g[y][x] = 1;
  }

  Matrix a[13];
  for (int i = 0; i <= 12; ++i) {
    a[i] = g;
  }

  scanf("%d", &nfish);
  while (nfish--) {
    int t, p[4];
    scanf("%d", &t);
    for (int i = 0; i < t; ++i) {
      scanf("%d", &p[i]);
    }
    p[t] = p[0];

    for (int i = 1; i <= 12; ++i) {
      for (int j = 0; j < n; ++j) {
        a[i][j][p[(i - 1) % t + 1]] = 0;
      }
    }
  }

  a[0].E();
  for (int i = 1; i <= 12; ++i) {
    a[0] = a[0] * a[i];
  }

  Matrix ans = kasumi(a[0], k / 12);
  for (int i = 1; i <= k % 12; ++i) {
    ans = ans * a[i];
  }

  printf("%d\n", ans[st][ed]);
  return 0;
}