AXi の最頻値が Y となるような Xi の組の数の偶奇を考えます。
具体的に N=3 の場合を考えてみましょう。
X1,X2,X3 がすべて異なるケースについて考えてみます。これは並び替えを考慮すると AXi の最頻値が Y になる組の数は必ず 6 の倍数になり、偶数です。
よってこのようなケースは考慮する必要がありません。
残りのケースについて考えます。まず X1,X2,X3 のうち 2 つは値が等しいがもう 1 つは等しくないケースですが、これは X1=X2,X1=X3 のケースだけ考えればいいです。さらに、 X1=X2=X3 のケースについて考える必要があります。
これら 2 パターンのケースですが、これらは「 X1=X2 であるようなケース」というように 1 つにまとめることができます。
さて、このように考えるべきパターンを限定してまとめあげることは一般の N でも可能でしょうか?
実は次のようにまとめるとができます。
- K を 2 進数表記した際に N=∑i=1B2bi と表せるものとする(bi<bi+1)。
このとき、 X1,X2,…XN の組について考慮すべきなのは、 X1=X2=…X2b1, X2b1+1=X2b1+2=⋯=X2b1+2b2, …, XK−2bB+1=…XK が成り立つような組のみである
証明は g1!g2!…gm!K! が奇数となる条件について、 Lucas の定理を用いて考えることでできます。
このことを用いて元の問題について考えると、最頻値は XK の値で決まり、残りの値の決め方は NB−1 通り存在するので、
- N が奇数、または K が 2 べきのとき、 Ai の排他的論理和
- そうでないとき、 0
が答えになります。