排他的論理和があるので、各ビット毎に考えることにします。以下、数値を2進法で表した時の2kの位を「kビット目」と呼びます。
a1,a2,⋯anは非負整数より0≤a1,a2,⋯an≤p<260なので、0ビット目から59ビット目まで考えれば良いです。
0≤i≤59とし、a1,a2,⋯anのiビット目の中で1がk個であるとします。
このようなビットの決め方はnCk通りであり、この時それらの1によってa1+a2+⋯+anはk⋅2i増加します。
よって、形式的冪級数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=pとなるようなビットの決め方はf0(x)f1(x)⋯f59(x)のxpの係数となります。
これにa1⊕a2⊕⋯⊕an=qを反映させます。0≤i≤59とし、0≤i≤59について、qのiビット目と「a1,a2,⋯anのiビット目の中で1である物の個数」の偶奇は一致します。
そのため、fi(x)についてqが偶数ならば奇数次、qが奇数ならば偶数次の項を0にして計算します。
しかし、この方法をナイーブに実装すると、形式的冪級数の長さは最小でもp+1になります。よって、TLE
やMLE
を引き起こしてしまうので、工夫が必要です。
ここで、pの0ビット目はa1,a2,⋯anの0ビット目のみで決まりますが、それ以外のビットは下位ビットからの繰り上がりに依存します。そのため、0ビット目から順に考えます。
p,qの0ビット目をそれぞれp0,q0とした時、
1. p0=q0=0の場合
f0(x)には偶数次の項のみが残ります。この後、1ビット目以降への繰り上がりさえ考慮すれば0ビット目についてはもう考える必要はありません。
そのため、p,q,a1,a2,⋯anを全て1ビット右シフトします。これにより、
- p→2p,q→2qとなります。
- a1,a2,⋯anの1ビット目から59ビット目について、a1+a2+⋯+anへの影響は半分になります。そのため、f1(x),f2(x),⋯f59(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)と同じです。
- 0ビット目については、0ビット目の和が0ならば繰り上がり0、2ならば繰り上がり1、4ならば繰り上がり2…となるので、f_0(x)\rightarrow\:_n{\rm C}_0x^0+\:_n{\rm C}_2x^1+\:_n{\rm C}_4x^2+\cdotsとなります。よって、f0(x)についても全ての項の次数は半分になります。
以上より、形式的冪級数の長さをおよそ半分にできました。
2. p0=q0=1の場合
1.と同様、p,q,a1,a2,⋯anを全て1ビット右シフトします。これにより、
- p→2p−1,q→2q−1となります。
- 1.と同様、f1(x),f2(x),⋯f59(x)の全ての項の次数は半分になります。
- 0ビット目については、0ビット目の和が1ならば繰り上がり0、3ならば繰り上がり1、5ならば繰り上がり2…となるので、f_0(x)\rightarrow\:_n{\rm C}_1x^0+\:_n{\rm C}_3x^1+\:_n{\rm C}_5x^2+\cdotsとなります。よって、f0(x)については、全ての項の次数について1を引いてから半分にします。
以上をp,qがともに0になるまで(最大60回)繰り返し、不必要な部分をカットしながらf0(x),f1(x)⋯を掛けていくことによって答えを求めます。掛け算によって冪級数の長さはおよそ2倍になりますが、ビットシフトによる圧縮によって半分になるので、冪級数の長さはずっとO(n)のままです。
3. p0=q0の場合
1度もビットシフトをしていない状態でp0=q0ならば解なしですが、それ以外の場合は下位ビットからの繰り上がりがあるため解なしとは限りません。この場合も、「それまでの積に、q0=0ならば奇数次の項、q0=1ならば偶数次の項を消去したものを掛け、p0=0ならば偶数次の項、q0=1ならば奇数次の項のみを取り出して次数を下げる」とすれば良いです。例えば、上記1.,2.よりp0=q0ならば、p0=0,1双方の場合について1ビットシフト後のf0(x)には奇数次・偶数次双方の項があるので、f1(x)に奇数次の項しかなくてもf0(x)f1(x)には偶数次の項があります。よって、q1=1,p1=0でも解なしとは限りません。
まとめ
以上より、この問題はビット毎に形式的冪級数を考え、それを順番に掛けていけば良いことが分かりました。よって、計算量はO(nlognlogp)となります。冪級数の積を求める際はmod環上での畳み込みを利用しましょう。
解答例
modintやconvolutionはAC Libraryを参照しました。解答例では引用箇所を示しておきます。(コードそのものは長すぎるので載せません。)
質問・誤りがある場合
Twitterに連絡ください。ID : @YS55749378