結果
問題 | 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 matrixmatrix 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-placevoid 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);}