SRM 650 Div1 easy : TaroFillingAStringDiv1

問題概要 :
長さNの文字列がある
初期状態ではそのうちのいくつかに'A'か'B'が書かれていて、
その他は何も書かれていない
これから何も書かれていない場所に'A'か'B'を書いていく
ただし何も書かれていない場所全てに'A'か'B'を書い後、隣接する２つの場所が同じ英小文字であるような場所の数が最小でなければならない ( このような場所のペアをuglinessという )
uglinessが最小となるような'A'と'B'の割り当て方は何通り存在するか？
答えを1000000007で割った余りを返せ

解法 :
'.'を何も書かれていない場所とする

A(奇数個 '.' が続く)A の場合, 最小のuglinessの数は０個
A ... A なら A BAB A のように両端と異なるものを割り当てればよいから
これより、両端が同じ英小文字でその間の空の場所の数が奇数ならその割り当て方は一意に定まる

A(偶数個 '.' が続く)A の場合, 最小のuglinessの数は１個
A .. A なら A BB A, A AB A, または A BA A のいずれか
A .... A について考える
A B..B A , この場合は同じ状態に戻るので再帰的に処理を続ける
A A..B A , この場合は既に１つuglinessができているのでその後の割り当て方は一意に定まる
A B..A A , この場合は１つ前の場合と同様で、割り当て方は一意に定まる

これらより、 A(偶数個 '.' が続く)A の場合は( 空白の数+1 )だけ割り当て方が存在することが分かる

A(奇数個 '.' が続く)Bの場合、最小のuglinessの数は1個
A ... B なら A BAA B, A BBA B, A ABA B, A BAB B のいずれか
A A...A B と A B...B B の場合は既に１つuglinessが1個あるのでその後の割り当て方は一意に定まる
その他の場合は再帰的に割り当てることになる

結局、この場合 2 + ( 連続する'.'の数 / 2 * 2 ) だけ割り当て方が存在することが分かる

連続する'.'の数が０か１の場合は割り当て方は一意に定まるので注意
また、これから割り当てる場所の両端のうち片方が '.' ならその割り当て方も一意に定まるので注意すること

コード :

typedef long long ll;
const int IINF = INT_MAX;
const ll MOD = 1000000007LL;

typedef pair<int,char> ic;

class TaroFillingAStringDiv1 {
public:
  
  ll compute(char prev_c,char next_c,int space){
    if( prev_c == '.' || next_c == '.' ) {
      return 1LL;
    } else {
      if( space == 0 ) return 1LL;
      if( prev_c == next_c ) {
        if( space == 1 ) return 1LL;
        if( space & 1 ) { // odd
          return 1LL;
        } else { // even
          return ( 1LL + (ll)space ) % MOD;
        }
      } else {
        if( space == 1 ) return 2LL;
        if( space & 1 ) { // odd
          ll multi = space / 2;
          return ( 2LL + multi * 2LL ) % MOD;
        } else { // even
          return 1LL;
        }
      }
    }
    return 1LL;
  }

  int getNumber( int N, vector <int> p, string s ) {
    deque<ic> deq;
    rep(i,p.size()) deq.push_back(ic(p[i]-1,s[i]));
    sort(deq.begin(),deq.end());
    if( deq[0].first != 0 ) deq.push_front(ic(0,'.'));
    if( deq.back().first != N-1 ) deq.push_back(ic(N-1,'.'));
    ll ret = 1;
    REP(i,1,deq.size()){
      char prev_c = deq[i-1].second;
      char next_c = deq[ i ].second;
      int free_space = deq[i].first - deq[i-1].first - 1;
      ( ret *= compute(prev_c,next_c,free_space) ) %= MOD;
    }
    return ret;
  }
};