この解説では各値 \(a,b,c,x,y,z\) の下から \(i\) ビット目の値を \(a_i,b_i,c_i,x_i,y_i,z_i\) と表記します。

\(\mathrm{O} (NM) \) 解法

まず、ビットごとに条件を考えます。

• \(x_i = 0,y_i = 0\) の場合

  • \((a_i,b_i,c_i) = (0,0,0)\) の1組が条件を満たします。総和は0です。

• \(x_i = 1,y_i = 1\) の場合

  • \((a_i,b_i,c_i) = (1,1,1)\) の1組が条件を満たします。総和は3です。

• \(x_i = 0,y_i = 1\) の場合

  • 総和が1になるような組 : \((a_i,b_i,c_i) = (0,0,1) , (0,1,0) , (1,0,0) \) の3組が条件を満たします。
  • 総和が2になるような組 : \((a_i,b_i,c_i) = (0,1,1) , (1,0,1) , (1,1,0) \) の3組が条件を満たします。

• \(x_i = 1,y_i = 0\) の場合

  • 条件を満たす \((a_i,b_i,c_i)\) は存在しません。

また、\(z_i\) の条件を満たす必要があります。下の桁からの繰り上がりの値を \(\mathrm{carry}\) とすると、\(a_i + b_i + c_i + \mathrm{carry} \equiv z_i \pmod{2}\) であることが求められます。

よって、\(x_i,y_i,z_i\)と下の桁からの繰り上がりの値 \(\mathrm{carry}\) が 定まっているとき、\((a_i,b_i,c_i)\) の選び方は \(0,1,3\) 通りのいずれかになります。

以下のような桁DPを考えます。

\(DP[i][\mathrm{carry}][r] = b\)
\(i\) : 下から\(i\)ビットが決定した状態 (\(0 \leq i \leq N\))
\(\mathrm{carry}\) : 一つ下の桁からの繰り上がり\((0 \leq \mathrm{carry} \leq 2)\)
\(r\) : 現在までの \((a_i,b_i,c_i)\) の選び方の総積を\(M\)で割った余り \((0 \leq r < M)\)
\(b\) : そのような状態に到達可能かのbool値

\(DP[0][0][1] = \mathrm{true}\) と初期化します。

\(i\) 桁目から \(i+1\) 桁目への推移を考えます。
あり得る\((x_i,y_i,z_i)\)の組を全通り試します。これは最大 \(8\) 通りです。
\(x_i,y_i,z_i\)と下の桁からの繰り上がりの値 \(\mathrm{carry}\) が定まっているとき、\((a_i,b_i,c_i)\) の選び方は \(0,1,3\) 通りのいずれかとなります。また、次の桁への繰り上がりも \({a_i + b_i + c_i + \mathrm{carry}}\) を \(2\) で切り捨て除算した値として定まります。よって、遷移先を \(\mathrm{O}(1)\) で求めることができます。

全ての計算が終わった後、各 \(k\) について、\(DP[N][0][k]\) が \(\mathrm{true}\) ならば \(f(x,y,z) \equiv k \pmod{M}\) であるような \({x,y,z}\)が存在します。そうでないとき、存在しません。

このDPは状態数が \(\mathrm{O}(NM)\) 、各状態から次の状態への遷移が \(\mathrm{O}(1)\) で可能であるため \(\mathrm{O}(NM)\) でこの問題を解くことができました。

\(\mathrm{O} (N^2 + M) \) 解法

今回の制約では\(M \leq 10^6\) であるため、上記の解法で実行制限時間内に答えを求めるのは難しいです。よって、上記の解法を高速化することを考えます。

以下の \(f(x,y,z)\) の性質を用います。

\(f(x,y,z)\) は \(0\) か非負整数 \(k\) を用いて \(3^{k}\) の形で表すことのできる数である。

各ビット\(i\) における \((a_i,b_i,c_i)\) の選び方は \(0,1,3\) 通りのいずれかであり、この積は必ず\(0\) または \(3^{k}\) の形で表すことのできる数となります。

上記の性質から、 \(\mathrm{O} (NM) \) 解法では \((a_i,b_i,c_i)\) の選び方の総積を\(M\)で割った余りを取っていた部分を、\((a_i,b_i,c_i)\) の選び方が \(3\) 通りであったようなビット \(i\) の個数として持つことができます。
この値は \( \mathrm{O}(N) \) で抑えることができるため、\(\mathrm{O}(N^2 + M)\) でこの問題を解くことができます。
\(f(x,y,z) = 0\) のパターンが存在するかどうかの情報を追加で持つ必要がある点に注意してください。

\(\mathrm{O} (N^2/w +M) \) 解法 (おまけ)

上記の \(\mathrm{O} (N^2 + M)\) の解法のDP部分は簡単にbitsetで高速化することができます。