SRM531 Div1 Medium(500) MonsterFarm

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;
}};