結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
|
提出日時 | 2021-01-15 22:15:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 3,489 bytes |
コンパイル時間 | 1,145 ms |
コンパイル使用メモリ | 113,280 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-27 23:10:27 |
合計ジャッジ時間 | 3,862 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
#include <iostream> #include <algorithm> #include <numeric> #include <vector> #include <string> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <iomanip> #include <functional> #include <bitset> #include <limits> #include <cstdio> #include <cmath> #include <cassert> #include <random> #ifdef DEBUG #include "library/Utility/debug.cpp" #else #define debug(...) #endif #define rep(i,n) for(int i=0;i<(n);++i) #define EL '\n' #define print(i) std::cout << (i) << '\n' #define all(v) (v).begin(), (v).end() using lnt = long long; struct FIO{FIO(){std::cin.tie(0);std::ios_base::sync_with_stdio(0);std::cout<<std::fixed<<std::setprecision(15);}}fIO; template<typename T> using V = std::vector<T>; template<typename T> void fill(V<T>&v) { for(T&e:v) std::cin >> e; } /*-*/ template <typename T = lnt> struct matrix // designed for int and modint(not yet validated) { const int n,m; std::vector<std::vector<T> > data; matrix(int n, int m, T k=0) : n(n),m(m),data(n,std::vector<T>(m,k)) {} matrix& operator+=(const matrix& a) { for(int i=0;i<a.n;++i) for(int j=0;j<a.m;++j) data[i][j]+=a.data[i][j]; return *this; } matrix& operator-=(const matrix& a) { for(int i=0;i<a.n;++i) for(int j=0;j<a.m;++j) data[i][j]-=a.data[i][j]; return *this; } matrix& operator*=(const matrix& a) { assert(m==a.n); matrix product(n,a.m); for(int i=0;i<n;++i) for(int j=0;j<a.m;++j) for(int k=0;k<m;++k) { product.data[i][j]+=data[i][k]*a.data[k][j]; if(product.data[i][j]>0) product.data[i][j]=1; } data=product.data; return *this; } matrix operator+(const matrix& a) const { return matrix(*this) += a; } matrix operator-(const matrix& a) const { return matrix(*this) -= a; } matrix operator*(const matrix& a) const { return matrix(*this) *= a; } bool operator==(const matrix& a) const { return data==a.data; } matrix transpose() const { matrix t(m,n); for(int i=0;i<n;++i) for(int j=0;j<m;++j) { t.data[j][i]=data[i][j]; } return t; } // square matrix matrix pow(lnt k) const { assert(n==m); matrix r(n,n), t(*this); for(int i=0;i<n;++i) { r.data[i][i]=1; } while(k) { if(k&1) r*=t; t*=t; k>>=1; } return r; } matrix det() const { assert(n==m); matrix A(*this); T d = A.GaussianElimination(); T o = 1; for(int i=0;i<n;++i) { o*=A.data[i][i]; } o/=d; return o; } // in-place void swap_rows(int a, int b) { std::swap(data[a],data[b]); } void multiply_row(int i, T v) { for(T& a:data[i]) a*=v; } void add_multiple_to_row(int i, int j, T v) { for(int k=0;k<m;++k) data[i][k]+=data[j][k]*v; } T GaussianElimination() { int i=0,j=0;T d=1; while(i<n && j<m) { int pivot = i; T max = data[i][j]; for(int x=i+1;x<n;++x) { if(max<data[x][j]) { pivot=x; max=data[x][j]; } } if(data[pivot][j]==0) { ++j; } else { if(i!=pivot) d*=-1; swap_rows(i, pivot); for(int x=i+1;x<n;++x) { T o = data[x][j]; d*=data[i][j]; multiply_row(x,data[i][j]); add_multiple_to_row(x,i,-o); } ++i; ++j; } } return d; } }; template <typename T> std::ostream& operator<<(std::ostream& o,const matrix<T>& a){ for(int i=0;i<a.n;++i) { for(int j=0;j<a.m;++j) o<<a.data[i][j]<<' '; o<<'\n'; } return o; } int main() { lnt n,m,t; std::cin >> n >> m >> t; matrix<lnt> g(n,n,0); rep(i,m) { int a,b; std::cin >> a >> b; g.data[a][b]=1; } matrix<lnt> x = g.pow(t); int ans=0; rep(i,n) ans+=x.data[0][i]; print(ans); }