Palindrome Again (UVa 11828)
問題
小文字からなる長さNの文字列Sがある。SからK個以下の文字を変更した回文文字列Pは何個存在するか。
1<=N<=1000
0<=K<=1000
解法
奇数の場合の中心を除いて、i番目の文字とn-i-1番目の文字が違う個数をp1、同じ個数をp2とする。i番目の文字とn-i-1番目の文字が同じ場所だけで考えると文字をj個変更した場合に作れる回文文字列の個数はO(1)で計算できる。もう一方の方も同様にO(1)で計算でき、これの総和とNが奇数かどうか,p1,p2を使えば全体の計算はO(K)でできる。
サンプルインプットがおかしいがi番目の文字とn-i-1番目の文字が同じかどうかだけで判断し計算すれば良い。
