VK Cup 2016 - Round 1 (Div.1 Edition) B. Bear and Polynomials

多項式 P(x) が与えられる。P(x) の係数をひとつだけ書き換えて Q(2)=0 となる多項式 Q(x) を作りたい。このような Q(x) の作り方は何通りあるだろうか。

まず P(2) の値を二進数で表してみよう。簡単のためにここでは P(2) > 0 とする。

図では左から 1 の位、2 の位、4 の位…の順になっている。

a[8] を a[8]-2047 に変更しても P(2) は 0 にならない。

f:id:pekempey:20160331235840p:plain

a[14] を a[14]-31 に変更しても P(2) は 0 にならない。

f:id:pekempey:20160331235845p:plain

この 2 つの例を見ればわかると思うが、変更する係数の位置は R - 32 以上 L 以下である必要がある。L, R は P(2) の 1 が最初に現れる場所と最後に現れる場所。

なぜなら、R - 33 以下になると最大限まで係数を減らしても最上位ビットを消すことができなくなり、L より大きくなると最下位ビットを消すことができなくなるからだ。

主係数以外が 0 になる場合も弾いてしまい Wrong Answer を出してしまった。