結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
|
提出日時 | 2021-01-15 22:12:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 123 ms / 2,000 ms |
コード長 | 7,164 bytes |
コンパイル時間 | 2,004 ms |
コンパイル使用メモリ | 203,908 KB |
最終ジャッジ日時 | 2025-01-17 19:33:10 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
#include <bits/stdc++.h>#ifdef DEBUG#include <Mylib/Debug/debug.cpp>#else#define dump(...) ((void)0)#endiftemplate <typename T, typename U>bool chmin(T &a, const U &b){return (a > b ? a = b, true : false);}template <typename T, typename U>bool chmax(T &a, const U &b){return (a < b ? a = b, true : false);}template <typename T, size_t N, typename U>void fill_array(T (&a)[N], const U &v){std::fill((U*)a, (U*)(a + N), v);}template <typename T, size_t N, size_t I = N>auto make_vector(const std::array<int, N> &a, T value = T()){static_assert(I >= 1);static_assert(N >= 1);if constexpr (I == 1){return std::vector<T>(a[N - I], value);}else{return std::vector(a[N - I], make_vector<T, N, I - 1>(a, value));}}template <typename T>std::ostream& operator<<(std::ostream &s, const std::vector<T> &a){for(auto it = a.begin(); it != a.end(); ++it){if(it != a.begin()) s << " ";s << *it;}return s;}template <typename T>std::istream& operator>>(std::istream &s, std::vector<T> &a){for(auto &x : a) s >> x;return s;}std::string YesNo(bool value){return value ? "Yes" : "No";}std::string YESNO(bool value){return value ? "YES" : "NO";}std::string yesno(bool value){return value ? "yes" : "no";}template <typename T>void putl(const T &value){std::cout << value << "\n";}template <typename Head, typename ... Tail>void putl(const Head head, const Tail &... tail){std::cout << head << " ";putl(tail ...);}namespace haar_lib {template <typename T, int &N>class vector_dyn {public:using value_type = T;private:std::vector<T> data_;public:vector_dyn(): data_(N){}vector_dyn(T value): data_(N, value){}vector_dyn(std::initializer_list<T> list): data_(N){int i = 0;for(auto it = list.begin(); it != list.end(); ++it) data_[i++] = *it;}vector_dyn(const vector_dyn &that): data_(that.data_){}template <typename U>vector_dyn(const std::vector<U> &that): data_(that.begin(), that.end()){}bool operator==(const vector_dyn &that){return data_ == that.data_;}bool operator!=(const vector_dyn &that){return !(*this == that);}auto& operator=(const vector_dyn &that){data_ = that.data_;return *this;}auto& operator+=(const vector_dyn &that){for(int i = 0; i < N; ++i) data_[i] += that.data_[i];return *this;}auto& operator-=(const vector_dyn &that){for(int i = 0; i < N; ++i) data_[i] -= that.data_[i];return *this;}friend auto dot(const vector_dyn &a, const vector_dyn &b){T ret = 0;for(int i = 0; i < N; ++i) ret += a.data_[i] * b.data_[i];return ret;}auto operator+(const vector_dyn &that) const {return vector(*this) += that;}auto operator-(const vector_dyn &that) const {return vector(*this) -= that;}auto& operator[](int i){return data_[i];}const auto& operator[](int i) const {return data_[i];}auto begin() const {return data_.begin();}auto end() const {return data_.end();}int size() const {return N;}friend std::ostream& operator<<(std::ostream &s, const vector_dyn &a){s << "{";for(auto it = a.data_.begin(); it != a.data_.end(); ++it){if(it != a.data_.begin()) s << ",";s << *it;}s << "}";return s;}};template <typename T, int &N>class square_matrix_dyn {public:using value_type = T;using vector_type = vector_dyn<T, N>;private:std::vector<vector_type> data_;public:square_matrix_dyn(): data_(N, vector_type()){}square_matrix_dyn(const T &val): data_(N, vector_type(val)){}square_matrix_dyn(std::initializer_list<std::initializer_list<T>> list): data_(N){int i = 0;for(auto it = list.begin(); it != list.end(); ++it){data_[i++] = vector_type(*it);}}square_matrix_dyn(const square_matrix_dyn &that): data_(that.data_){}square_matrix_dyn(const std::vector<std::vector<T>> &that): data_(N){for(int i = 0; i < N; ++i) data_[i] = that[i];}bool operator==(const square_matrix_dyn &that) const {return data_ == that.data_;}bool operator!=(const square_matrix_dyn &that) const {return !(*this == that);}auto& operator=(const square_matrix_dyn &that){data_ = that.data_;return *this;}auto& operator+=(const square_matrix_dyn &that){for(int i = 0; i < N; ++i) data_[i] += that.data_[i];return *this;}auto& operator-=(const square_matrix_dyn &that){for(int i = 0; i < N; ++i) data_[i] -= that.data_[i];return *this;}auto& operator*=(const square_matrix_dyn &that){square_matrix_dyn ret;for(int i = 0; i < N; ++i)for(int j = 0; j < N; ++j)for(int k = 0; k < N; ++k)ret[i][j] |= data_[i][k] * that.data_[k][j];//ret[i][j] += data_[i][k] * that.data_[k][j];return *this = ret;}const auto& operator[](int i) const {return data_[i];}auto& operator[](int i){return data_[i];}int size() const {return N;}static auto unit(){square_matrix_dyn ret;for(int i = 0; i < N; ++i) ret[i][i] = 1;return ret;}auto operator+(const square_matrix_dyn &that){return square_matrix_dyn(*this) += that;}auto operator-(const square_matrix_dyn &that){return square_matrix_dyn(*this) -= that;}auto operator*(const square_matrix_dyn &that){return square_matrix_dyn(*this) *= that;}auto pow(uint64_t p) const {auto ret = unit();auto a = *this;while(p > 0){if(p & 1) ret *= a;a *= a;p >>= 1;}return ret;}auto operator*(const vector_type &that){vector_type ret;for(int i = 0; i < N; ++i) ret[i] = dot(data_[i], that);return ret;}};}namespace haar_lib {}namespace solver {using namespace haar_lib;constexpr int m1000000007 = 1000000007;constexpr int m998244353 = 998244353;void init(){std::cin.tie(0);std::ios::sync_with_stdio(false);std::cout << std::fixed << std::setprecision(12);std::cerr << std::fixed << std::setprecision(12);std::cin.exceptions(std::ios_base::failbit);}static int N;void solve(){std::cin >> N;int M; std::cin >> M;int64_t T; std::cin >> T;square_matrix_dyn<int, N> mat;for(int i = 0; i < M; ++i){int a, b; std::cin >> a >> b;mat[b][a] = 1;}mat = mat.pow(T);for(int i = 0; i < N; ++i){for(int j = 0; j < N; ++j){std::cerr << mat[i][j] << " ";}std::cerr << "\n";}int ans = 0;for(int i = 0; i < N; ++i){if(mat[i][0]) ++ans;}std::cout << ans << "\n";}}int main(){solver::init();while(true){try{solver::solve();std::cout << std::flush;std::cerr << std::flush;}catch(const std::istream::failure &e){break;}catch(...){break;}}return 0;}