SRM531 Div1 Medium

500
行列累乗で挑んだけど、どうにも通らない。
行列やシミュレーションのようなアプローチだと mod が悪さをするらしく、複数の mod で試す必要があるらしい。
素直にグラフにしてやった。

path[ 0 ][ i ] == true
path[ i ][ i ] == true
out_degree[ i ] > 1
を満たす頂点が存在したら無限に増える。

const lli mod = 1000000007;

class MonsterFarm {
public:
  int numMonsters(vector <string> T) 
  {
    const int size = T.size();

    bool reach[size][size];
    fill(&reach[0][0], &reach[size - 1][size], 0);

    lli g[size][size];
    fill(&g[0][0], &g[size - 1][size], 0);

    int deg[size];
    fill(deg, deg + size, 0);

    for (int i = 0; i < (int)T.size(); ++i) {
      istringstream iss(T[i]);
      for (string s; iss >> s; ) {
        int j = atoi(s.c_str()) - 1;
        ++deg[i];
        ++g[i][j];
        reach[i][j] = true;
      }
    }


    for (int k = 0; k < (int)size; ++k) {
      for (int i = 0; i < (int)size; ++i) {
        for (int j = 0; j < (int)size; ++j) {
          reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
        }
      }
    }

    for (int i = 0; i < (int)size; ++i) {
      if (reach[0][i] && reach[i][i] && 1 < deg[i]) {
        return -1;
      }
    }

    lli dp[2][size];
    fill(&dp[0][0], &dp[2 - 1][size], 0);
    dp[0][0] = 1;
    
    for (int i = 0; i < (int)size; ++i) {
      int curr = i % 2;
      int next = (i + 1) % 2;
      for (int j = 0; j < (int)size; ++j) {
        dp[next][j] = 0;
      }
      for (int j = 0; j < (int)size; ++j) {
        for (int k = 0; k < (int)size; ++k) {
          dp[next][k] += dp[curr][j] * g[j][k];
          dp[next][k] %= mod;
        }
      }
    }

    lli sum = 0;
    for (int i = 0; i < (int)size; ++i) {
      sum += dp[0][i];
      sum %= mod;
    }
    return sum;
  }
};