結果

問題 No.1112 冥界の音楽
コンテスト
ユーザー yukudo
提出日時 2020-07-10 22:50:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 26 ms / 2,000 ms
コード長 2,622 bytes
コンパイル時間 1,880 ms
コンパイル使用メモリ 176,148 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-11 10:09:33
合計ジャッジ時間 3,177 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}


const ll MOD = ((ll)1e9)+7;

#define SZ(v) ((int)(v).size())
using Array = vector<ll>;
using Matrix = vector<Array>;

Matrix zero(int N){ return Matrix(N, Array(N)); }

Matrix identity(int N) {
  Matrix A = zero(N);
  REP(i, N) A[i][i] = 1;
  return A;
}

Matrix add(const Matrix &A, const Matrix& B){
  const int N = SZ(A);
  const int M = SZ(A[0]);
  Matrix C(N, Array(M));
  REP(i, N) REP(j, M) {
    C[i][j] += A[i][j] + B[i][j];
    if (C[i][j] >= MOD) C[i][j] %= MOD;
  }
  return C;
}

Array mul(const Matrix &A, const Array &x){
  const int N = SZ(A);
  const int M = SZ(A[0]);
  Array y(N);
  REP(i, N) REP(j, M) {
    y[i] += A[i][j] * x[j];
    y[i] %= MOD;
  }
  return y;
}

// A:[N,P] * B:[P,M] = C:[N,M]
Matrix mul(const Matrix &A, const Matrix& B) {
  const int N = SZ(A);
  const int P = SZ(A[0]);
  const int M = SZ(B[0]);
  Matrix C(N, Array(M));
  REP(i, N) REP(j, M) REP(k, P) {
    C[i][j] += A[i][k] * B[k][j];
    if (C[i][j] >= MOD) C[i][j] %= MOD;
  }
  return C;
}

Matrix pow(Matrix A, ll b) {
  Matrix C = identity(SZ(A));
  while (b > 0) {
    if ((b & 1) == 1) C = mul(C, A);
    A = mul(A, A);
    b >>= 1;
  }
  return C;
}



void print(const Matrix& A){
  REP(i, SZ(A)){
    REP(j, SZ(A[0])){
      cout << A[i][j] << " ";
    }
    cout << endl;
  }
  cout << "---------------------" << endl;
}


int encode(int t1, int t2) {
  return t1 * 6 + t2;
}

int main2() {
  int K = nextLong();
  int M = nextLong();
  ll N = nextLong();

  Matrix A = zero(36);

  REP(m, M) {
    int P = nextLong() - 1;
    int Q = nextLong() - 1;
    int R = nextLong() - 1;
    A[ encode(Q, R) ][ encode(P, Q) ] += 1;
  }

  // print(A);

  auto AA = pow(A, N-2);

  Array a = Array(36);
  REP(i, 1) REP(j, K)  a[encode(i, j)] = 1;

  // pv(ALL(a));
  auto b = mul(AA, a);

  // pv(ALL(b));

  ll ans = 0;
  REP(i, K) REP(j, K) {
    if (j == 0) {
      ans += b[encode(i, j)];
      ans %= MOD;
    }
  }

  cout << ans << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}
0