結果

問題 No.1340 おーじ君をさがせ
ユーザー zlnzln
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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);
}
0