cafelier@SRM

TCO Round1 1000

あとで | 11:49 |

普段mod演算は念のためlong longでやってるのだけど、それだとTLEした。intに変えて通しました。これは本番でいくら時間があっても気づけなかった予感。

static const int MODVAL = 1000000007;
int ADD(int x, int y) { return (x+y)%MODVAL; }
int SUB(int x, int y) { return (x-y+MODVAL)%MODVAL; }

class Unicorn {
public:
  int countWays(int R, int C, int L, int seed, string word) 
  {
    // input...
    char B[300][300];
    {
      int x = seed;
      int d = (65535 / L)+1;
      for (int r=0; r<R; r++)
        for (int c=0; c<C; c++) {
          x = (x * 25173 + 13849) % 65536;
          B[r][c] = (65+(x / d));
        }
    }

    // solve
    vector<int> cnt(C*R);
    for(int r=0; r<R; ++r)
    for(int c=0; c<C; ++c)
      if( B[r][c] == word[0] )
        cnt[r*C+c] = 1;

    for(int i=1; i<word.size(); ++i)
    {
      int total_cnt = 0;
      vector<int> c_cnt(C);
      vector<int> r_cnt(R);
      for(int r=0; r<R; ++r)
      for(int c=0; c<C; ++c)
        r_cnt[r]  = ADD( r_cnt[r], cnt[r*C+c]),
        c_cnt[c]  = ADD( c_cnt[c], cnt[r*C+c]),
        total_cnt = ADD(total_cnt, cnt[r*C+c]);

      vector<int> cnt2(C*R);
      for(int r=0; r<R; ++r)
      for(int c=0; c<C; ++c)
        if( B[r][c] == word[i] )
        {
          int x = total_cnt;

          for(int rr=r-1; rr<=r+1; ++rr) if(0<=rr && rr<R)
            x = SUB(x, r_cnt[rr]);
          for(int cc=c-1; cc<=c+1; ++cc) if(0<=cc && cc<C)
            x = SUB(x, c_cnt[cc]);

          for(int rr=r-1; rr<=r+1; ++rr) if(0<=rr && rr<R)
          for(int cc=c-1; cc<=c+1; ++cc) if(0<=cc && cc<C)
            x = ADD(x, cnt[rr*C+cc]);

          for(int rr=r-2; rr<=r+2; rr+=4) if(0<=rr && rr<R)
          for(int cc=c-2; cc<=c+2; cc+=4) if(0<=cc && cc<C)
            x = SUB(x, cnt[rr*C+cc]);

          cnt2[r*C+c] = x;
        }
      cnt.swap(cnt2);
    }

    int live = 0;
    for(int r=0; r<R; ++r)
    for(int c=0; c<C; ++c)
      live = ADD(live, cnt[r*C+c]);
    return live;
  }
};

ユニコーンのいけないところを列単位行単位でまとめておいて数えるとO(1)でひとつの遷移を計算できる