■171F - Strivore
oofに5文字挿入
**o**o**f**
とでもして最後以外は25種を最後は26種類をいれれる
f1 = 1 + 25x + 25^2x^2 + 25^3x^3..............
f2 = 1 + 26x + 26^2x^2 + 26^3x^3..............
f1^N * f2の係数が答え
f1 = 1/(1-25x)
f2 = 1/(1-26x)
f1^k = Σ(n + K - 1,K - 1)25^n*x^n
■172F - Unfair Nim
桁dp
桁dpは上から見るか、下から見るかという問題があって、
これは下から見るタイプ。
ビットごとに見ていき、下からa0からa1に移すことでxorの値を調整していく
移す際にa0は繰り下がりが、a1は繰り上がりが発生するので、それも遷移に組み込む
dp[i][j][j];//i:桁目、j:繰り下がりの有無、k:繰り上がりの有無
■173F - Intervals on Tree
森の頂点数= 森の中の辺の数 + 連結成分の数
すなわち
連結成分の数 = 森の頂点数 -森の中の辺の数
頂点、辺それぞれに対して、森の頂点数、森の中の辺の数として何回カウントされるかを考えれば良い。
■174F - Range Set Query
BIT
ポイントはクエリを順番に扱うのではなく、扱いやすい順番で扱うこと。
この問題の場合だと右端順にソートして扱うと良い。
区間内に同じ色の玉があるとカウントが出来ないので
区間内の最右の位置のみをBITにもたせておく
区間から出たら更新すれば良い
サンプルでいうと
2565217972を
1110011100
0110111100
0011111100
0001111100
0000111100
0000011101
0000001101
0000000111
0000000011
0000000001
このような感じで考える。
■175F - Making Palindrome
真ん中をまず決めます。
その前に回文は奇数長と偶数長があることを注意します
つまり文字列"abc"の中心の候補は7個になります。
そのそれぞれの中で、中心になる権利がある場所を列挙します
abcだと左右の2ケースになります。
この時点ですでに回分でなければどちらかが余るので
左:空、右:"abc"
左:"abc"、右:空
のような状態を保持しておき、それに他の文字列を空の方にあてがい、
新たな{空,文字列},{空、文字列}な状態を作ります。
文字列はsの頭か、後ろからの部分列なので
状態数が種類×文字数程度で収まるのでダイクストラが可能になります。
