AXiA_{X_i} の最頻値が YY となるような XiX_i の組の数の偶奇を考えます。

具体的に N=3N=3 の場合を考えてみましょう。
X1,X2,X3X_1,X_2,X_3 がすべて異なるケースについて考えてみます。これは並び替えを考慮すると AXiA_{X_i} の最頻値が YY になる組の数は必ず 66 の倍数になり、偶数です。
よってこのようなケースは考慮する必要がありません。
残りのケースについて考えます。まず X1,X2,X3X_1,X_2,X_3 のうち 22 つは値が等しいがもう 11 つは等しくないケースですが、これは X1=X2,X1X3X_1=X_2,X_1\neq X_3 のケースだけ考えればいいです。さらに、 X1=X2=X3X_1=X_2=X_3 のケースについて考える必要があります。
これら 22 パターンのケースですが、これらは「 X1=X2X_1=X_2 であるようなケース」というように 11 つにまとめることができます。

さて、このように考えるべきパターンを限定してまとめあげることは一般の NN でも可能でしょうか?
実は次のようにまとめるとができます。

  • KK22 進数表記した際に N=i=1B2biN=\sum_{i=1}^{B} 2^{b_i} と表せるものとする(bi<bi+1b_i<b_{i+1})。
    このとき、 X1,X2,XNX_1,X_2,\dots X_N の組について考慮すべきなのは、 X1=X2=X2b1, X2b1+1=X2b1+2==X2b1+2b2, , XK2bB+1=XKX_1=X_2=\dots X_{2^{b_1}},\ X_{2^{b_1}+1}=X_{2^{b_1}+2}=\dots =X_{2^{b_1}+2^{b_2}},\ \dots ,\ X_{K-2^{b_B}+1}=\dots X_{K} が成り立つような組のみである

証明は K!g1!g2!gm!\frac{K!}{g_1!g_2!\dots g_m!} が奇数となる条件について、 Lucas の定理を用いて考えることでできます。

このことを用いて元の問題について考えると、最頻値は XKX_K の値で決まり、残りの値の決め方は NB1N^{B-1} 通り存在するので、

  • NN が奇数、または KK22 べきのとき、 AiA_i の排他的論理和
  • そうでないとき、 00

が答えになります。