結果
問題 | No.1112 冥界の音楽 |
ユーザー |
|
提出日時 | 2020-07-10 22:03:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 6,535 bytes |
コンパイル時間 | 2,031 ms |
コンパイル使用メモリ | 196,560 KB |
最終ジャッジ日時 | 2025-01-11 18:31:45 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#line 1 "main.cpp" #include <bits/stdc++.h> #line 2 "/home/user/Library/utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 4 "/home/user/Library/modulus/modpow.hpp" inline int32_t modpow(uint_fast64_t x, uint64_t k, int32_t MOD) { assert (/* 0 <= x and */ x < (uint_fast64_t)MOD); uint_fast64_t y = 1; for (; k; k >>= 1) { if (k & 1) (y *= x) %= MOD; (x *= x) %= MOD; } assert (/* 0 <= y and */ y < (uint_fast64_t)MOD); return y; } #line 5 "/home/user/Library/modulus/modinv.hpp" inline int32_t modinv_nocheck(int32_t value, int32_t MOD) { assert (0 <= value and value < MOD); if (value == 0) return -1; int64_t a = value, b = MOD; int64_t x = 0, y = 1; for (int64_t u = 1, v = 0; a; ) { int64_t q = b / a; x -= q * u; std::swap(x, u); y -= q * v; std::swap(y, v); b -= q * a; std::swap(b, a); } if (not (value * x + MOD * y == b and b == 1)) return -1; if (x < 0) x += MOD; assert (0 <= x and x < MOD); return x; } inline int32_t modinv(int32_t x, int32_t MOD) { int32_t y = modinv_nocheck(x, MOD); assert (y != -1); return y; } #line 4 "/home/user/Library/modulus/mint_core.hpp" /** * @brief quotient ring / 剰余環 $\mathbb{Z}/n\mathbb{Z}$ */ template <int32_t MOD> struct mint { int32_t value; mint() : value() {} mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {} mint(int32_t value_, std::nullptr_t) : value(value_) {} explicit operator bool() const { return value; } inline mint<MOD> operator + (mint<MOD> other) const { return mint<MOD>(*this) += other; } inline mint<MOD> operator - (mint<MOD> other) const { return mint<MOD>(*this) -= other; } inline mint<MOD> operator * (mint<MOD> other) const { return mint<MOD>(*this) *= other; } inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; } inline mint<MOD> & operator -= (mint<MOD> other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; } inline mint<MOD> & operator *= (mint<MOD> other) { this->value = (uint_fast64_t)this->value * other.value % MOD; return *this; } inline mint<MOD> operator - () const { return mint<MOD>(this->value ? MOD - this->value : 0, nullptr); } inline bool operator == (mint<MOD> other) const { return value == other.value; } inline bool operator != (mint<MOD> other) const { return value != other.value; } inline mint<MOD> pow(uint64_t k) const { return mint<MOD>(modpow(value, k, MOD), nullptr); } inline mint<MOD> inv() const { return mint<MOD>(modinv(value, MOD), nullptr); } inline mint<MOD> operator / (mint<MOD> other) const { return *this * other.inv(); } inline mint<MOD> & operator /= (mint<MOD> other) { return *this *= other.inv(); } }; template <int32_t MOD> mint<MOD> operator + (int64_t value, mint<MOD> n) { return mint<MOD>(value) + n; } template <int32_t MOD> mint<MOD> operator - (int64_t value, mint<MOD> n) { return mint<MOD>(value) - n; } template <int32_t MOD> mint<MOD> operator * (int64_t value, mint<MOD> n) { return mint<MOD>(value) * n; } template <int32_t MOD> mint<MOD> operator / (int64_t value, mint<MOD> n) { return mint<MOD>(value) / n; } template <int32_t MOD> std::istream & operator >> (std::istream & in, mint<MOD> & n) { int64_t value; in >> value; n = value; return in; } template <int32_t MOD> std::ostream & operator << (std::ostream & out, mint<MOD> n) { return out << n.value; } #line 5 "/home/user/Library/number/matrix_template.hpp" template <typename T, size_t H, size_t W> using matrix = std::array<std::array<T, W>, H>; template <typename T, size_t A, size_t B, size_t C> matrix<T, A, C> operator * (matrix<T, A, B> const & a, matrix<T, B, C> const & b) { matrix<T, A, C> c = {}; REP (y, A) REP (z, B) REP (x, C) c[y][x] += a[y][z] * b[z][x]; return c; } template <typename T, size_t H, size_t W> std::array<T, H> operator * (matrix<T, H, W> const & a, std::array<T, W> const & b) { std::array<T, H> c = {}; REP (y, H) REP (z, W) c[y] += a[y][z] * b[z]; return c; } template <typename T, size_t H, size_t W> matrix<T, H, W> operator + (matrix<T, H, W> const & a, matrix<T, H, W> const & b) { matrix<T, H, W> c; REP (y, H) REP (x, W) c[y][x] = a[y][x] + b[y][x]; return c; } template <typename T, size_t N> std::array<T, N> operator + (std::array<T, N> const & a, std::array<T, N> const & b) { std::array<T, N> c; REP (i, N) c[i] = a[i] + b[i]; return c; } template <typename T, size_t H, size_t W> matrix<T, H, W> zero_matrix() { return {}; } template <typename T, size_t N> matrix<T, N, N> unit_matrix() { matrix<T, N, N> a = {}; REP (i, N) a[i][i] = 1; return a; } template <typename T, size_t N> matrix<T, N, N> powmat(matrix<T, N, N> x, int64_t k) { matrix<T, N, N> y = unit_matrix<T, N>(); for (; k; k >>= 1) { if (k & 1) y = y * x; x = x * x; } return y; } #line 5 "main.cpp" using namespace std; constexpr int MOD = 1000000007; mint<MOD> solve(int k, int m, int64_t n, const vector<int> & p, const vector<int> & q, const vector<int> & r) { constexpr int K = 6; assert (k <= K); auto pack = [&](int a, int b) { return a * K + b; }; matrix<mint<MOD>, K * K, K * K> f = {}; REP (i, m) { f[pack(q[i], r[i])][pack(p[i], q[i])] += 1; } array<mint<MOD>, K * K> x = {}; REP (b, K) { x[pack(0, b)] += 1; } array<mint<MOD>, K * K> y = powmat(f, n - 2) * x; mint<MOD> ans = 0; REP (a, K) { ans += y[pack(a, 0)]; } return ans; } // generated by online-judge-template-generator v4.4.0 (https://github.com/kmyk/online-judge-template-generator) int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); constexpr char endl = '\n'; int K; int M; int64_t N; cin >> K >> M; vector<int> P(M), Q(M), R(M); cin >> N; REP (i, M) { cin >> P[i] >> Q[i] >> R[i]; -- P[i]; -- Q[i]; -- R[i]; } auto ans = solve(K, M, N, P, Q, R); cout << ans << endl; return 0; }