CodeChef Match Challenge 2020 - Inverse of a Function

• 問題
• AC

まずは与えられた数列の美しさを求める方法を考える。数列$(a_i)$に$i$桁目が$1$の数が$d(i)$個含まれているとき、$d(i)$個から奇数個選べば残りの数をどう選んでもxorの$i$桁目が$1$になる。つまり、$i$桁目だけに限ってxorの総和を取ると、$d(i) > 0$なら$2^i$が

$$\begin{aligned} & 2^{N-d(i)} \biggl( \binom{d(i)}{1} + \binom{d(i)}{3} + ... \biggr) \\ = & 2^{N-d(i)} 2^{d(i)-1} \\ = & 2^{N-1} \end{aligned}$$

個足されることになる。すなわち、$i$桁目が立っている数が$(a_i)$の中に1つでもあれば、$i$桁目の総和は$2^{N-1} 2^i$であり、ひとつもなければ$0$である。したがって、全体の総和はbitwise orを使って

$$2^{N-1} \bigvee_{i=1}^{N}a_i$$

と表すことができる。これが$(a_i)$の美しさである。

次に$F(N, B) :=$ 長さ$N$で美しさ$B$の数列の数、を求める方法を考える。上の式を見ると、$B$が与えられたときに$B/2^{N-1}$の立っているビットを考えればよいことがわかる。つまり、$B/2^{N-1}$の$i$桁目が$1$なら、$N$個の数のうちの少なくとも$1$つの数の$i$桁目が$1$であればよく、$i$桁目に限定した$N$個の数の選び方は$2^N-1$通りとなる。いっぽう、$B/2^{N-1}$の$i$桁目が$0$なら、$N$個の数の対応する$i$桁目はすべて$0$でなければならないので、選び方は$1$通りである。したがって、整数$x$の立っているビットの総数を$c(x)$で表すとき、

$$F(N, B) = \begin{cases} (2^N-1)^{c(B/2^{N-1})} & \qquad (Bが2^{N-1}で割り切れる)\\ 0 & \qquad (それ以外) \end{cases}$$

と書ける。

さて、解くべき問題は$F(N, B) \equiv X \mod M$を満たす最小の$B$を求めるというものだった。上の式を見ると、$(2^N-1)^k \equiv X \mod M$を満たす最小の$k \ge 0$が求まれば、$k$個の$1$を並べて$N-1$回左シフトしたものが求める最小の$B$ということになる。これで離散対数問題に帰着できた。

ただし、上の式からわかるように、$N \ge 2$の時は美しさ$1$の数列がないので、$X=0$に対しては常に$1$が答えということになる。（もちろん$M=0$なら$0$）。