Wrong Answer on test 233 (Hard Version) - #602 div2 f
#math
解法
数列 h の i, i + 1 番目が
1. x x
と同じとき,
a の i 番目が何でも, シフトしても x との一致不一致は変わらない
a の i 番目は k 通り
2. x y
と異なるとき
a の i 番目が
2-1. x のとき
h の i 番目と一致してたのに i + 1 番目と一致しなくなる
2-2. y のとき
h の i 番目と一致してなかったのに i + 1 番目と一致する
2-2. xでもyでもないとき
1. と同じ
ただし, a の i 番目は k - 2 通り
求める解は
2-2. - 2-1. > 0
となる数列 a の個数
他にありうるのは,
2-2. - 2-1. < 0
2-2. - 2-1. = 0
ここで, 2-1. , 2-2. の対称性より
(1), (2) の個数は等しい
よって, (1)は言い換えると
(3)の求め方
h の i, i + 1 番目が等しくなるとき
a の i 番目は k 通り
残った要素で,
2-2. を全探索する (O(N) )
2-1. はそれと個数が等しくなる
残りは各々 k - 2 通り (pow にO(log N) )
ポイント
a の要素は独立に決められる
問題は個数で, 位置は関係ない
