結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
![]() |
提出日時 | 2021-01-15 21:49:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 116 ms / 2,000 ms |
コード長 | 2,497 bytes |
コンパイル時間 | 4,223 ms |
コンパイル使用メモリ | 204,516 KB |
最終ジャッジ日時 | 2025-01-17 19:08:29 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000000template <typename T,typename F0,typename F1>struct matrix{F0 func0;F1 func1;vector<vector<T>> value;int height,width;T init_value0,init_value1;matrix(vector<vector<T>> X,F0 f0,F1 f1,T iv0,T iv1):func0(f0),func1(f1){height = X.size();width = X[0].size();value = X;init_value0 = iv0,init_value1 = iv1;}matrix(int h,int w,F0 f0,F1 f1,T iv0,T iv1):func0(f0),func1(f1){vector<vector<T>> d(h,vector<T>(w,iv0));height = h,width = w;value = d;init_value0 = iv0,init_value1 = iv1;}void set_1(){for(int i=0;i<height;i++){for(int j=0;j<width;j++){if(i==j)value[i][j] = init_value1;else value[i][j]=init_value0;}}}void show(){for(int i=0;i<height;i++){for(int j=0;j<width;j++){if(j!=0)cout<<' ';cout<<value[i][j];}cout<<endl;}}matrix &operator=(const matrix &another){value = another.value;height = another.height;width = another.width;return *this;}matrix &operator*=(const matrix &another){matrix<T,decltype(func0),decltype(func1)> R(height,another.width,func0,func1,init_value0,init_value1);for(int i=0;i<R.value.size();i++){for(int j=0;j<R.value[i].size();j++){R.value[i][j]=init_value0;for(int k=0;k<width;k++){R.value[i][j] = func0(R.value[i][j],func1(value[i][k],another.value[k][j]));}}}value = R.value;return (*this);}matrix operator*(const matrix &another)const{return (matrix(*this)*=another);}matrix beki(long long cnt){matrix<T,decltype(func0),decltype(func1)> R(height,width,func0,func1,init_value0,init_value1);R.set_1();auto temp = *this;while(cnt!=0LL){if(cnt%2==1){R *= temp;}temp *= temp;cnt/=2;}return R;}};int main(){int N,M;cin>>N>>M;long long T;cin>>T;vector<vector<int>> A(N+1,vector<int>(N+1,0));rep(i,M){int a,b;cin>>a>>b;A[a][b] = 1;}rep(i,N){A[i][N] = 1;A[N][N] = 1;}auto f0 = [](int a,int b){return a|b;};auto f1 = [](int a,int b){return a&b;};matrix<int,decltype(f0),decltype(f1)> AA(A,f0,f1,0LL,1);AA = AA.beki(T);vector<vector<int>> X(1,vector<int>(N+1,0));X[0][0] = 1;matrix<int,decltype(f0),decltype(f1)> XX(X,f0,f1,0LL,1);XX *= AA;int ans= 0;rep(i,N){ans += XX.value[0][i];}cout<<ans<<endl;return 0;}