RUPC 2016 day3 F: Kitsuchiri
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=F
解法
S=rev(S) が成り立てば左右対称である。等価判定はハッシュを使うと楽。
[L,R] に x を加算するというのは、
- hash(S) に x*(bL+bL+1+...+bR) を足す
- hash(rev(S)) に x*(bL'+bL'+1+...+bR') を足す
ということ。なお L'=N-1-R, R'=N-1-L。
加算が簡単にできるので hash(S) と hash(rev(S)) を変数として持っておけば簡単に更新ができる。
これは Rolling Hash を以下の式で求めた場合の話なので、ハッシュの計算法が異なれば式は変わってくる。
$$ hash(S) = \sum_{i=0}^{N-1} S[i] b^i $$
多分想定解は違う気がする。