#510643 (C++17) No.1112 冥界の音楽

• 問題: No.1112 冥界の音楽
• ユーザー: ninoinui
• 提出日時: 2020-07-11 13:43:55
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 43 ms / 2,000 ms
• コード長: 6,755 bytes
• コンパイル時間: 2,936 ms
• コンパイル使用メモリ: 201,424 KB
• 最終ジャッジ日時: 2025-01-11 19:45:27
• ジャッジサーバーID （参考情報）: judge2 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 34

ソースコード

#include <bits/stdc++.h>
using namespace std;

#define EPS 1e-10
#define MOD 1000000007

template<typename T> class Matrix : public vector<vector<T>> {
private:
  int r, c;
public:
  inline int row() const {
    return r;
  }
  inline int column() const {
    return c;
  }
  Matrix(int n, int m, T val = 0) {
    r = n, c = m;
    for (int i = 0; i < n; i++) {
      this -> push_back(vector<T>(m, val));
    }
  }
  Matrix operator + (const Matrix &another) const {
    Matrix<T> X(r, c);
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        X.at(i).at(j) = (*this).at(i).at(j) + another.at(i).at(j);
      }
    }
    return X;
  }
  Matrix operator + (const T val) const {
    Matrix<T> X(r, c);
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        X.at(i).at(j) = (*this).at(i).at(j) + val;
      }
    }
    return X;
  }
  Matrix operator - (const Matrix &another) const {
    Matrix<T> X(r, c);
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        X.at(i).at(j) = (*this).at(i).at(j) - another.at(i).at(j);
      }
    }
    return X;
  }
  Matrix operator - (const T val) const {
    Matrix<T> X(r, c);
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        X.at(i).at(j) = (*this).at(i).at(j) - val;
      }
    }
    return X;
  }
  vector<T> operator * (const vector<T> &another) const {
    vector<T> vec(r, 0);
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        vec.at(i) += (*this).at(i).at(j) * another.at(j);
      }
    }
    return vec;
  }
  Matrix operator * (const Matrix &another) const {
    Matrix<T> X(r, another.c);
    for (int i = 0; i < r; i++) {
      for (int k = 0; k < c; k++) {
        for (int j = 0; j < (another.c); j++) {
          X.at(i).at(j) += (*this).at(i).at(k) * another.at(k).at(j);
        }
      }
    }
    return X;
  }
  Matrix operator - () const {
    Matrix<T> X(r, c);
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        X.at(i).at(j) = -(*this).at(i).at(j);
      }
    }
    return X;
  }
  int rank() const {
    int res = 0;
    Matrix B(r, c);
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        B.at(i).at(j) = (*this).at(i).at(j);
      }
    }
    for (int i = 0; i < c; i++) {
      if (res == r) return res;
      int pivot = res;
      for (int j = res + 1; j < r; j++) {
        if (abs(B.at(j).at(i)) > abs(B.at(pivot).at(i))) {
          pivot = j;
        }
      }
      if (abs(B.at(pivot).at(i)) < EPS) continue;
      swap(B.at(pivot), B.at(res));
      for (int j = i + 1; j < c; j++) {
        B.at(res).at(j) /= B.at(res).at(i);
      }
      for (int j = res + 1; j < r; j++) {
        for (int k = i + 1; k < c; k++) {
          B.at(j).at(k) -= B.at(res).at(k) * B.at(j).at(i);
        }
      }
      res++;
    }
    return res;
  }
  T det() const {
    T ans = 1;
    Matrix B(r, r);
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        B.at(i).at(j) = (*this).at(i).at(j);
      }
    }
    for (int i = 0; i < c; i++) {
      int pivot = i;
      for (int j = i + 1; j < r; j++) {
        if (abs(B.at(j).at(i)) > abs(B.at(pivot).at(i))) {
          pivot = j;
        }
      }
      if (abs(B.at(pivot).at(i)) < EPS) return (T)0;
      if (pivot != i) swap(B.at(i), B.at(pivot)), ans = -ans;
      ans *= B.at(i).at(i);
      for (int j = i + 1; j < r; j++) {
        for (int k = c - 1; k >= i; k--) {
          B.at(j).at(k) -= B.at(i).at(k) * B.at(j).at(i) / B.at(i).at(i);
        }
      }
    }
    return ans;
  }
  Matrix inverse() const {
    Matrix B(r, 2 * r);
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < r; j++) {
        B.at(i).at(j) = (*this).at(i).at(j);
      }
    }
    for (int i = 0; i < r; i++) {
      B.at(i).at(r + i) = 1;
    }
    for (int i = 0; i < r; i++) {
      int pivot = i;
      for (int j = i; j < r; j++) {
        if (abs(B.at(j).at(i)) > abs(B.at(pivot).at(i))) {
          pivot = j;
        }
      }
      swap(B.at(i), B.at(pivot));
      for (int j = i + 1; j < 2 * r; j++) {
        B.at(i).at(j) /= B.at(i).at(i);
      }
      for (int j = 0; j < r; j++) {
        if (i != j) {
          for (int k = i + 1; k < 2 * r; k++) {
            B.at(j).at(k) -= B.at(j).at(i) * B.at(i).at(k);
          }
        }
      }
    }
    Matrix res(r, r);
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < r; j++) {
        res.at(i).at(j) = B.at(i).at(r + j);
      }
    }
    return res;
  }
};

template<typename T> vector<T> eq_solve(const Matrix<T> &A, const vector<T> &b) {
  int n = A.row();
  Matrix<T> B(n, n + 1);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      B.at(i).at(j) = A.at(i).at(j);
    }
  }
  for (int i = 0; i < n; i++) {
    B.at(i).at(n) = b.at(i);
  }
  for (int i = 0; i < n; i++) {
    int pivot = i;
    for (int j = i; j < n;j++) {
      if (abs(B.at(j).at(i)) > abs(B.at(pivot).at(i))) {
        pivot = j;
      }
    }
    swap(B.at(i), B.at(pivot));
    for (int j = i + 1; j <= n; j++) {
      B.at(i).at(j) /= B.at(i).at(i);
    }
    for (int j = 0; j < n; j++) {
      if (i != j) {
        for (int k = i + 1; k <= n; k++) {
          B.at(j).at(k) -= B.at(j).at(i) * B.at(i).at(k);
        }
      }
    }
  }
  vector<T> res(n);
  for (int i = 0; i < n; i++) {
    res.at(i) = B.at(i).at(n);
  }
  return res;
}

template<typename T> Matrix<T> pow(Matrix<T> A, long cnt) {
  int n = A.row();
  Matrix<T> B(n, n);
  for (int i = 0; i < n; i++) {
    B.at(i).at(i) = 1;
  }
  while (cnt > 0) {
    if (cnt & 1) B = B * A;
    A = A * A;
    cnt >>= 1;
  }
  return B;
}

template<typename T> Matrix<T> mod_mul(Matrix<T> &A, Matrix<T> &B) {
  Matrix<T> X(A.row(), B.column());
  for (int i = 0; i < A.row(); i++) {
    for (int k = 0; k < A.column(); k++) {
      for (int j = 0; j < B.column(); j++) {
        X.at(i).at(j) = (X.at(i).at(j) + (long) A.at(i).at(k) * B.at(k).at(j)) % MOD;
      }
    }
  }
  return X;
}

template<typename T> Matrix<T> mod_pow(Matrix<T> A, long cnt) {
  int n = A.row();
  Matrix<T> B(n, n);
  for (int i = 0; i < n; i++) {
    B.at(i).at(i) = 1;
  }
  while (cnt > 0) {
    if (cnt & 1) B = mod_mul(B, A);
    A = mod_mul(A, A);
    cnt >>= 1;
  }
  return B;
}

int main() {
  int K, M;
  long N;
  cin >> K >> M >> N;
  Matrix<int> mat(K * K, K * K);
  for (int i = 0; i < M; i++) {
    int P, Q, R;
    cin >> P >> Q >> R;
    P--, Q--, R--;
    mat.at(P * K + Q).at(Q * K + R) = 1;
  }
  Matrix<int> mat2 = mod_pow(mat, N - 2);
  long ans = 0;
  for (int i = 0; i < K; i++) {
    for (int j = 0; j < K; j++) {
      ans += mat2.at(i).at(j * K);
      ans %= MOD;
    }
  }
  cout << ans << "\n";
}