結果
問題 | No.1112 冥界の音楽 |
ユーザー |
|
提出日時 | 2020-07-12 13:26:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 2,870 bytes |
コンパイル時間 | 1,327 ms |
コンパイル使用メモリ | 114,752 KB |
最終ジャッジ日時 | 2025-01-11 19:58:35 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <cstdio> #include <ctime> #include <assert.h> #include <chrono> #include <random> #include <numeric> #include <set> using namespace std; typedef long long int ll; using ull = unsigned long long; constexpr ll mod=1e9+7; template<class T> struct Mat{ vector<vector<T>> A; Mat(){} Mat(size_t n,size_t m):A(n,vector<T>(m,0)){} Mat(size_t n):A(n,vector<T>(n,0)){}; size_t height() const{ return A.size(); } size_t width() const{ return A[0].size(); } inline const vector<T> &operator[](int k) const{ return A.at(k); } inline 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(); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ (*this)[i][j]=((*this)[i][j]+B[i][j])%mod; } } return (*this); } Mat &operator-=(const Mat &B){ size_t n=height(),m=width(); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ (*this)[i][j]=((*this)[i][j]-B[i][j])%mod; if((*this)[i][j]<0)(*this)[i][j]+=mod; } } return (*this); } Mat &operator*=(const Mat &B){ int n=height(),m=B.width(),p=width(); assert(p==B.height()); vector<vector<T>> C(n,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])%mod; } } } A.swap(C); return (*this); } Mat &operator^=(ll k){ Mat B=Mat::I(height()); while(k){ if(k%2)B*=(*this); (*this)*=(*this); k>>=1LL; } A.swap(B.A); 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); } Mat operator^(const Mat &B) const{ return (Mat(*this)^=B); } }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int k,m; cin >> k >> m; ll n; cin >> n; Mat<ll> mat(k*k); vector<int> p(m),q(m),r(m); for(int i=0;i<m;i++){ cin >> p[i] >> q[i] >> r[i]; p[i]--; q[i]--; r[i]--; mat[p[i]*k+q[i]][q[i]*k+r[i]]=1; } mat^=(n-2); ll res=0; for(int i=0;i<k;i++){ for(int j=0;j<k;j++){ (res+=mat[i][j*k])%=mod; } } printf("%lld\n",res); }