SRM531 Div1 Medium(500) MonsterFarm
Nステップ、モンスターを増殖させる。その後のNステップでモンスターが増えなければ、モンスターの数は有限。増えるなら無限に増える。ノードがNのグラフをN-1回辿れば、到達可能なノードには全て到達するから。1000000007と0を区別する必要がある。
#include <string> #include <vector> #include <sstream> #include <numeric> using namespace std; class MonsterFarm{public: int numMonsters( vector <string> transforms ) { const int M = 1000000007; int N = (int)transforms.size(); vector<vector<int> > trans(N,vector<int>(N)); for ( int i=0; i<N; i++ ) { stringstream ss(transforms[i]); int t; while ( ss>>t ) trans[i][t-1]++; } vector<long long> T(N); // 各モンスターの数 vector<bool> Tp(N); // 各モンスターが1匹以上か否か T[0] = 1; Tp[0] = true; bool f = true; for ( int i=0; i<2*N; i++ ) { vector<long long> P = T; vector<bool> Pp = Tp; T = vector<long long>(N); Tp = vector<bool>(N); for ( int j=0; j<N; j++ ) { for ( int k=0; k<N; k++ ) { T[k] += trans[j][k]*P[j]; T[k] %= M; if ( Pp[j] && trans[j][k]>0 ) Tp[k] = true; } // N回目以降のループでモンスターが増えるなら× if ( i>=N && Pp[j] && accumulate(trans[j].begin(),trans[j].end(),0)>1 ) f = false; } } return f ? int(accumulate(T.begin(),T.end(),0LL)%M) : -1; }};