結果

問題 No.1112 冥界の音楽
コンテスト
ユーザー suta28407928
提出日時 2020-07-10 22:53:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 4,485 bytes
コンパイル時間 1,141 ms
コンパイル使用メモリ 107,480 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-15 04:53:44
合計ジャッジ時間 2,242 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
#include <unordered_map>
#include <fstream>
#include <complex>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef pair<int,int> pii;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(int i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,-1,0,1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
    if(a>b){
        a = b; return true;
    }
    else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
    if(a<b){
        a = b; return true;
    }
    else return false;
}
template<typename T> inline void print(T &a){
    rep(i,a.size()) cout << a[i] << " ";
    cout << "\n";
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
    cout << a << " " << b << " " << c << "\n";
}
const ll mod = 1e9 + 7;
//const int mod = 998244353;

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

using mint = modint<mod>;

vvl matmul(vvl &a, vvl &b){
    vvl c(a.size(), vl(b[0].size()));
    for(int i=0; i<a.size(); i++){
        for(int k=0; k<b.size(); k++){
            for(int j=0; j<b[0].size(); j++){
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
            }
        }
    }
    return c;
}

vvl matpow(vvl a, ll n){
    vvl b(a.size(), vl(a.size()));
    for(int i=0; i<a.size(); i++) b[i][i] = 1;
    while(n > 0){
        if(n & 1) b = matmul(b,a);
        a = matmul(a,a);
        n >>= 1;
    }
    return b;
}

ll modpow(ll x, ll n, ll mod){
    ll res = 1;
    while(n > 0){
        if(n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

ll a[6][6][6];

int main(){
    ll K,m,n; cin >> K >> m >> n;
    rep(i,m){
        ll p,q,r; cin >> p >> q >> r;
        p--; q--; r--;
        a[p][q][r] = 1;
    }
    ll ans = 0;
    if(n == 3){
        rep(j,K) ans += a[0][j][0];
        cout << ans << "\n";
        return 0;
    }
    ll L = K*K;
    vvl b(L,vl(L,0));
    vl c(L,0);
    rep(j,K){
        rep(k,K){
            c[j*K + k] += a[0][j][k];
        }
    }
    rep(i,K){
        rep(j,K){
            rep(k,K){
                b[j*K+k][i*K+j] += a[i][j][k];
            }
        }
    }
    b = matpow(b,n-4);
    rep(i,L){
        if(!a[i/K][i%K][0]) continue;
        ll sum = 0;
        rep(j,L){
            sum += b[i][j] * c[j] % mod;
            sum %= mod;
        }
        ans += sum;
        ans %= mod;
    }
    cout << ans << "\n";
}
0