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

• 問題: No.1112 冥界の音楽
• ユーザー: ninoinui
• 提出日時: 2020-07-11 13:43:55
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 27 ms / 2,000 ms
• コード長: 6,755 bytes
• コンパイル時間: 2,232 ms
• コンパイル使用メモリ: 202,380 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-04-21 02:03:34
• 合計ジャッジ時間: 3,291 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	3 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	4 ms; 5,376 KB
testcase_14	AC	11 ms; 5,376 KB
testcase_15	AC	3 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	4 ms; 5,376 KB
testcase_18	AC	4 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	7 ms; 5,376 KB
testcase_22	AC	7 ms; 5,376 KB
testcase_23	AC	3 ms; 5,376 KB
testcase_24	AC	2 ms; 5,376 KB
testcase_25	AC	2 ms; 5,376 KB
testcase_26	AC	2 ms; 5,376 KB
testcase_27	AC	2 ms; 5,376 KB
testcase_28	AC	2 ms; 5,376 KB
testcase_29	AC	2 ms; 5,376 KB
testcase_30	AC	9 ms; 5,376 KB
testcase_31	AC	2 ms; 5,376 KB
testcase_32	AC	10 ms; 5,376 KB
testcase_33	AC	2 ms; 5,376 KB
testcase_34	AC	1 ms; 5,376 KB
testcase_35	AC	2 ms; 5,376 KB
testcase_36	AC	27 ms; 5,376 KB

ソースコード

#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";
}