結果

問題 No.1112 冥界の音楽
コンテスト
ユーザー tonakai
提出日時 2020-07-11 00:35:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 492 ms / 2,000 ms
コード長 10,436 bytes
コンパイル時間 3,203 ms
コンパイル使用メモリ 201,388 KB
最終ジャッジ日時 2025-01-11 19:24:44
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define uniq(v) v.erase(unique(v.begin(),v.end()),v.end())
#define lb(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define ub(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
using Pair = pair<ll,pair<int,int>>;
#define pq priority_queue<Pair, vector<Pair>, greater<Pair>> 
const ll mod=1000000007;
//const ll mod=998244353;
const ld pi=acos(-1.0);
const ll INF = 1LL<<61;
template<class T>bool chmax(T &a, const T &b) { 
  if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) {
  if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる


//——————————————————modint———————————————————————————


#define MAX 2000000  // 階乗をいくつまで計算するか
 
class mint {
    ll val;
    static ll *invs, *facts, *finvs;
 
    // 階乗, 逆元, 階乗の逆元をMAXまで求める
    bool initMint() {
        invs[1] = 
        facts[0] = facts[1] =
        finvs[0] = finvs[1] = 1;
        for (int i=2; i<=MAX; i++) {
            invs[i]  = -invs[MOD % i] * (MOD / i) % MOD;
            facts[i] = facts[i - 1] * i % MOD;
            finvs[i] = finvs[i - 1] * invs[i] % MOD;
        }
        return true;
    }
 
public:
    static ll MOD; // modの元
 
    // 初期化 値を引数に与えなかった場合はval=0としておく
    mint(ll init = 0) : val(init) {
        static bool call_once = initMint(); // static変数の性質により一度だけ呼ばれる
        assert(call_once); // unusedの回避
        if (val < 0 || val >= MOD) val %= MOD;
        if (val < 0) val += MOD;   // 0以上であることを保証
    }
 
    inline ll toll() { return this->val; }
 
    // 代入
    void operator=(const mint &r) { this->val = r.val; }
    void operator=(const ll &r) { *this = mint(r); }
 
    // 足し算; 符号反転; 引き算
    mint operator+(const mint &r) {
        ll ans = this->val + r.val;
        if (ans >= MOD) ans -= MOD;
        return mint(ans);
    }
    mint operator-() {
        ll ans = MOD - this->val;
        return mint(ans);
    }
    mint operator-(const mint &r) {
        mint rr = r;
        return *this + (-rr);
    }
 
    //かけ算; 逆元; わり算
    mint operator*(const mint &r) {
        ll ans = this->val * r.val;
        return mint(ans);
    }
    mint inv() {
        assert(this->val != 0);
        if (this->val == 1) return mint(1);
 
        mint p, q = *this, m(0), n(1), r, c;
        p.val = MOD;
        while (q.val > MAX) {
            r = p.val % q.val;
            c = m.val - n.val * (p.val / q.val);
            p = q, q = r, m = n, n = c;
        }
        return n * invs[q.val];
    }
    mint operator/(const mint &r) { return *this * mint(r).inv(); }
    mint operator%(const mint &r) { return mint(this->val % r.val); }
 
    // ++ -- 前付きと後ろ付き
    void operator++() { ++this->val; }
    void operator++(int a) {
        a = 0;
        this->val++;
    }
    void operator--() { --this->val; }
    void operator--(int a) {
        a = 0;
        this->val--;
    }
 
    // 四則演算&代入
    void operator+=(const mint &r) { *this = *this + r; }
    void operator-=(const mint &r) { *this = *this - r; }
    void operator*=(const mint &r) { *this = *this * r; }
    void operator/=(const mint &r) { *this = *this / r; }
    void operator%=(const mint &r) { *this = *this % r; }
 
    // べき乗
    mint pow(long n) {
        if (n < 0)
            return inv().pow(-n);  // 逆元の-n乗
        else if (n == 0)
            return mint(1);
 
        mint half = pow(n / 2);
        if (n % 2)
            return *this * half * half;
        else
            return half * half;
    }
    mint pow(mint n) { return pow(n.val); }
 
    // 順列
    mint per(mint _k) {
        assert(this->val <= MAX);
        const ll n = this->val, k = _k.val;
        if (k < 0 || k > n) return 0;
        if (k == 0) return 1;
        if (k == n) return facts[n];
        return mint(facts[n]) * finvs[n - k];
    }

    // コンビネーション
    mint com(mint _k) {
        assert(this->val <= MAX);
        const ll n = this->val, k = _k.val;
        if (k < 0 || k > n) return 0;
        if (k == 0 || k == n) return 1;
        return mint(facts[n]) * finvs[k] * finvs[n - k];
    }
 
    // 階乗
    mint fact() { 
        assert(this->val <= MAX);
        return mint(facts[this->val]);
    }
 
    friend bool operator<(const mint &l, const mint &r) { return l.val < r.val; }
    friend bool operator>(const mint &l, const mint &r) { return l.val > r.val; }
    friend bool operator==(const mint &l, const mint &r) { return l.val == r.val; }
    friend bool operator!=(const mint &l, const mint &r) { return !(l.val == r.val); }
    friend bool operator<=(const mint &l, const mint &r) { return !(l.val > r.val); }
    friend bool operator>=(const mint &l, const mint &r) { return !(l.val < r.val); }
 
    friend ostream &operator<<(ostream &os, const mint &out) {
        os << out.val;
        return os;
    }
    friend istream &operator>>(istream &is, mint &in) {
        ll inl;
        is >> inl;
        in.val = inl % mint::MOD;
        return is;
    }
};
 
// べき乗
inline mint mpow(ll n, ll k) { return mint(n).pow(k); }
// 順列
inline mint mper(ll n, ll k) { return mint(n).per(k); }
// コンビネーション
inline mint mcom(ll n, ll k) { return mint(n).com(k); }
// 階乗
inline mint mfac(ll n) { return mint(n).fact(); }
 
// static変数
ll *mint::invs  = new ll[MAX+1];
ll *mint::facts = new ll[MAX+1];
ll *mint::finvs = new ll[MAX+1];
 
ll mint::MOD = (ll)1e9 + 7;

//—————————————————————————————————————————————————



//——————————————————matrix　行列———————————————————————————


template< class T >
struct Mat {
    std::vector< std::vector< T > > A;
    Mat() {}
    Mat(size_t n, size_t m) : A(n, std::vector< T >(m, 0)) {}
    Mat(size_t n) : A(n, std::vector< T >(n, 0)) {};
    size_t height() const {
        return (A.size());
    }
    size_t width() const {
        return (A[0].size());
    }
    inline const std::vector< T > &operator[](int k) const {
        return (A.at(k));
    }
    inline std::vector< T > &operator[](int k) {
        return (A.at(k));
    }
    static Mat I(size_t n) {
        Mat mat(n);
        for (int i = 0; i < n; i++) mat[i][i] = 1;
        return (mat);
    }
    Mat &operator+=(const Mat &B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                (*this)[i][j] += B[i][j];
        return (*this);
    }
    Mat &operator-=(const Mat &B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                (*this)[i][j] -= B[i][j];
        return (*this);
    }
    Mat &operator*=(const Mat &B) {
        size_t n = height(), m = B.width(), p = width();
        assert(p == B.height());
        std::vector< std::vector< T > > C(n, std::vector< T >(m, 0));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < p; k++)
                    C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);
        A.swap(C);
        return (*this);
    }
    Mat operator+(const Mat &B) const {
        return (Mat(*this) += B);
    }
    Mat operator-(const Mat &B) const {
        return (Mat(*this) -= B);
    }
    Mat operator*(const Mat &B) const {
        return (Mat(*this) *= B);
    }
    friend std::ostream &operator<<(std::ostream &os, Mat &p) {
        size_t n = p.height(), m = p.width();
        for (int i = 0; i < n; i++) {
            os << "[";
            for (int j = 0; j < m; j++) {
                os << p[i][j] << (j + 1 == m ? "]\n" : ",");
            }
        }
        return (os);
    }
    
    T determinant() {
        Mat B(*this);
        assert(width() == height());
        T ret = 1;
        for (int i = 0; i < width(); i++) {
            int idx = -1;
            for (int j = i; j < width(); j++) {
                if (B[j][i] != 0) idx = j;
            }
            if (idx == -1) return (0);
            if (i != idx) {
                ret *= -1;
                swap(B[i], B[idx]);
            }
            ret *= B[i][i];
            T vv = B[i][i];
            for (int j = 0; j < width(); j++) {
                B[i][j] /= vv;
            }
            for (int j = i + 1; j < width(); j++) {
                T a = B[j][i];
                for (int k = 0; k < width(); k++) {
                    B[j][k] -= B[i][k] * a;
                }
            }
        }
        return (ret);
    }
    
    
    Mat pow(int64_t k) const {
        auto res = I(A.size());
        auto M = *this;
        while (k > 0) {
            if (k & 1) {
                res *= M;
            }
            M *= M;
            k >>= 1;
        }
        return res;
    }
};



//—————————————————————————————————————————————————






int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll k,m,n;
  cin>>k>>m>>n;

  Mat<mint> mat(k*k);

  rep(i,m){
    int p,q,r;
    cin>>p>>q>>r;
    p--;q--;r--;
    mat[p*k+q][q*k+r]=1;
  }

  auto ma=mat.pow(n-2);

  mint ans=0;

  rep(i,k) {
    rep(j,k) {
      ans+=ma[i][j*k];
    }
  }

  cout << ans << endl;

}
0