SUM-XOR Equation 2

2 secs 1024 MB
YSatUT's icon YSatUT

排他的論理和があるので、各ビット毎に考えることにします。以下、数値を22進法で表した時の2k2^kの位を「kkビット目」と呼びます。 a1,a2,ana_1,a_2,\cdots a_nは非負整数より0a1,a2,anp<2600\leq a_1,a_2,\cdots a_n\leq p<2^{60}なので、00ビット目から5959ビット目まで考えれば良いです。

0i590\leq i\leq 59とし、a1,a2,ana_1,a_2,\cdots a_niiビット目の中で11kk個であるとします。 このようなビットの決め方はnCk_n{\rm C}_k通りであり、この時それらの11によってa1+a2++ana_1+a_2+\cdots+a_nk2ik\cdot 2^i増加します。 よって、形式的冪級数f_i(x)=\:_n{\rm C}_0x^0+\:_n{\rm C}_1x^{2^i}+\:_n{\rm C}_2x^{2\cdot2^i}+\cdots+\:_n{\rm C}_nx^{n\cdot2^i}\left(=(1+x^{2^i})^n\right)を考えると、a1+a2++an=pa_1+a_2+\cdots+a_n=pとなるようなビットの決め方はf0(x)f1(x)f59(x)f_0(x)f_1(x)\cdots f_{59}(x)xpx^pの係数となります。

これにa1a2an=qa_1\oplus a_2\oplus\cdots\oplus a_n=qを反映させます。0i590\leq i\leq 59とし、0i590\leq i\leq 59について、qqiiビット目と「a1,a2,ana_1,a_2,\cdots a_niiビット目の中で11である物の個数」の偶奇は一致します。 そのため、fi(x)f_i(x)についてqqが偶数ならば奇数次、qqが奇数ならば偶数次の項を00にして計算します。

しかし、この方法をナイーブに実装すると、形式的冪級数の長さは最小でもp+1p+1になります。よって、TLEMLEを引き起こしてしまうので、工夫が必要です。 ここで、pp00ビット目はa1,a2,ana_1,a_2,\cdots a_n00ビット目のみで決まりますが、それ以外のビットは下位ビットからの繰り上がりに依存します。そのため、00ビット目から順に考えます。 p,qp,q00ビット目をそれぞれp0,q0p_0,q_0とした時、

1. p0=q0=0p_0=q_0=0の場合

f0(x)f_0(x)には偶数次の項のみが残ります。この後、11ビット目以降への繰り上がりさえ考慮すれば00ビット目についてはもう考える必要はありません。 そのため、p,q,a1,a2,anp,q,a_1,a_2,\cdots a_nを全て1ビット右シフトします。これにより、

  • pp2,qq2p\rightarrow\frac{p}{2}, q\rightarrow\frac{q}{2}となります。
  • a1,a2,ana_1,a_2,\cdots a_n11ビット目から5959ビット目について、a1+a2++ana_1+a_2+\cdots+a_nへの影響は半分になります。そのため、f1(x),f2(x),f59(x)f_1(x),f_2(x),\cdots f_{59}(x)全ての項の次数は半分になります。特に、f_1(x)\rightarrow\:_n{\rm C}_0x^0+\:_n{\rm C}_1x^1+\:_n{\rm C}_2x^2+\cdots+\:_n{\rm C}_nx^n\left(=(1+x)^n\right)となり、これはビットシフト前のf0(x)f_0(x)と同じです。
  • 00ビット目については、00ビット目の和が00ならば繰り上がり0022ならば繰り上がり1144ならば繰り上がり22…となるので、f_0(x)\rightarrow\:_n{\rm C}_0x^0+\:_n{\rm C}_2x^1+\:_n{\rm C}_4x^2+\cdotsとなります。よって、f0(x)f_0(x)についても全ての項の次数は半分になります。

以上より、形式的冪級数の長さをおよそ半分にできました。

2. p0=q0=1p_0=q_0=1の場合

1.と同様、p,q,a1,a2,anp,q,a_1,a_2,\cdots a_nを全て1ビット右シフトします。これにより、

  • pp12,qq12p\rightarrow\frac{p-1}{2}, q\rightarrow\frac{q-1}{2}となります。
  • 1.と同様、f1(x),f2(x),f59(x)f_1(x),f_2(x),\cdots f_{59}(x)の全ての項の次数は半分になります。
  • 00ビット目については、00ビット目の和が11ならば繰り上がり0033ならば繰り上がり1155ならば繰り上がり22…となるので、f_0(x)\rightarrow\:_n{\rm C}_1x^0+\:_n{\rm C}_3x^1+\:_n{\rm C}_5x^2+\cdotsとなります。よって、f0(x)f_0(x)については、全ての項の次数について1を引いてから半分にします。

以上をp,qp,qがともに0になるまで(最大60回)繰り返し、不必要な部分をカットしながらf0(x),f1(x)f_0(x),f_1(x)\cdotsを掛けていくことによって答えを求めます。掛け算によって冪級数の長さはおよそ2倍になりますが、ビットシフトによる圧縮によって半分になるので、冪級数の長さはずっとO(n)O(n)のままです。

3. p0q0p_0\neq q_0の場合

1度もビットシフトをしていない状態でp0q0p_0\neq q_0ならば解なしですが、それ以外の場合は下位ビットからの繰り上がりがあるため解なしとは限りません。この場合も、「それまでの積に、q0=0q_0=0ならば奇数次の項、q0=1q_0=1ならば偶数次の項を消去したものを掛け、p0=0p_0=0ならば偶数次の項、q0=1q_0=1ならば奇数次の項のみを取り出して次数を下げる」とすれば良いです。例えば、上記1.,2.よりp0=q0p_0=q_0ならば、p0=0,1p_0=0,1双方の場合について1ビットシフト後のf0(x)f_0(x)には奇数次・偶数次双方の項があるので、f1(x)f_1(x)に奇数次の項しかなくてもf0(x)f1(x)f_0(x)f_1(x)には偶数次の項があります。よって、q1=1,p1=0q_1=1,p_1=0でも解なしとは限りません。

まとめ

以上より、この問題はビット毎に形式的冪級数を考え、それを順番に掛けていけば良いことが分かりました。よって、計算量はO(nlognlogp)O(n\log n\log p)となります。冪級数の積を求める際はmod環上での畳み込みを利用しましょう。

解答例

modintやconvolutionはAC Libraryを参照しました。解答例では引用箇所を示しておきます。(コードそのものは長すぎるので載せません。)

解答.cpp

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378