問題概要
'A', 'B' の 2 種類の文字からなる， 文字の文字列を考える．今，文字列の長さ及びいくつかの位置の文字は決まっていて，各
に対して，
文字目の文字は
である．それ以外の位置の文字はまだ決まっていない．
文字列の "ugliness"（醜さ）を，文字列中で同じ文字が隣接している箇所の総数と定義する．
ugliness を最小にするように残りの文字を決めたとき，作ることができる文字列の総数を として，
の値を求めよ．
解法
と書きます．
文字列長がそれなりに長いので，未決定の文字を 1 文字ずつ決めていくような戦略をとることができません．より効率的な方法を考える必要があります．
ある文字に ugliness に関して影響を及ぼすのは隣接する文字だけなので，2 文字以上離れた文字同士は影響し合いません．つまり，予め決まっている文字を挾んで反対側にある文字は ugliness について全く寄与しません．すなわち互いに独立です．このことと，確定している文字に挟まれた部分の総数は 個であることを踏まえると，確定された文字に挟まれた部分の選択肢の総数をある程度高速に求められれば，それぞれの選択肢の数を掛け合わせることで全体の答えを求めることができます．
確定された文字に挟まれた部分を「クラスタ」と呼ぶことにします．
実は，題意より ugliness を最小にしなければならないということを考えると，各クラスタに於ける選択肢（文字の割り当て方）の総数は簡単に求めることができます．
まず，確定された位置の内，最も末尾寄りのものを考えると，確定された文字が 'A' ならば，"BABA..." という文字列に定まり，確定された文字が 'B' ならば ABAB..." という文字列に定まります．先頭側も同様です．
次に，確定された文字に挟まれた部分について考えます．この部分については，そのクラスタの文字列長と，それを挟む文字が重要になります．ugliness の増加を 0 にできる場合はそれ以外の選択肢が無いのでそのように割り当てなければなりません．そのような場合とは，
- 挟む文字が同一で，文字列長が奇数の場合
- 挟む文字が異なり，文字列長が偶数の場合
の 2 パターンあります．この場合，片側から ugliness を増やさないように（直前の文字と異なる文字を使うように）割り当てていくと，反対側とも ugliness を増加させずに繋げることができます．言い換えると，右側と左側から ugliness を増加させないように文字列を構築したとき，2 つの文字列は一致しているということです．
先程の条件を満たさない場合，そのクラスタで ugliness が 1 だけ増加することになります．両側から ugliness を増加させないように文字列を構築したとき，2 つの文字列は完全に逆（片方で 'A' のところは他方で 'B' になる．vice versa）になります．すなわち，クラスタの中のどこかの位置で，他方の文字列に切り替わる部分が生じ，その位置こそが ugliness を増加させる位置となります．そのような位置は，先頭の手前と末尾の後ろを含めた，文字と文字の間なので，クラスタの文字列長 に対し，
の選択肢があります．従って，（計算中の）答えに
を乗じることで，そのクラスタに於ける選択肢の数を加味できます．
全てのクラスタについて上記のように処理すれば，全体での答えを求めることができます．各クラスタについての処理は で完了するので答えの計算は
時間ですが，予めインデックスについてソートしておく必要があるので，全体の処理は
時間になります．．
using LL = long long; template < typename T = int > using VT = vector< T >; #define REP2( i, n ) REP3( i, 0, n ) #define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define GET_REP( a, b, c, F, ... ) F #define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ ) #define ALL( c ) ( c ).begin(), ( c ).end() #define SZ( v ) ( (int)( v ).size() ) #define BI back_inserter #define MP make_pair #define fst first #define snd second constexpr int MOD = 1000000007; class TaroFillingAStringDiv1 { public: int getNumber( int N, vector <int> position, string value ) { VT< pair< int, char > > ps; transform( ALL( position ), value.begin(), BI( ps ), []( const int p, const char c ){ return MP( p, c ); } ); sort( ALL( ps ) ); LL res = 1; REP( i, SZ( ps ) - 1 ) { const int d = ps[ i + 1 ].fst - ps[i].fst - 1; if ( ( ps[i].snd == ps[ i + 1 ].snd && d % 2 ) || ( ps[i].snd != ps[ i + 1 ].snd && d % 2 == 0 ) ) { continue; } ( res *= d + 1 ) %= MOD; } return res; } };
