本問題は、次の値を計算することに帰着できます。

• 操作を終了することなく\(N\) 枚並べたときに、xor で \(1\) が作れるような数列を数え上げよ

以下、この問題を解きます（「答」といった場合もこれを指します）。

線形代数の基礎的な用語を仮定します。また、次の記号や結果を用います（公式解説参照）

• \(q\) - 階乗 \([\mathbf{n}]_q!\)
• \(q\) - 二項係数 \(\binom{\mathbf{n}}{\mathbf{k}}_q\)
• \(\mathbb{F}_q\) 上の \(n\) 次元ベクトル空間の \(k\) 次元部分空間の個数は \(\binom{\mathbf{n}}{\mathbf{k}}_q\) である

以下、\(q=2\) とします。また、\(O(N+B)\) 時間の前計算により、\([\mathbf{n}]_q!\) やその逆元を \(n\leq \max\{N, B\}\) に対して \(O(1)\) 時間で取得できるようにしておきます。

---

[1]

以下、\(N, B\) を定数とします。

\(a_n, b_n\) を次のように定義します：

• \(n\) 次元ベクトル空間 \(V\) を固定する。相異なる \(V\) の要素からなる長さ \(N\) の列 \((v_1, \ldots, v_N)\) であって、\(\mathrm{span}(v_1, \ldots, v_N) = V\) となるものの個数を \(a_n\) と定める。

• \(n\) 次元ベクトル空間 \(V\) を固定する。相異なる \(V\) の要素からなる長さ \(N\) の列 \((v_1, \ldots, v_N)\) の個数を \(b_n\) と定める。

\(b_n\) を \(\mathrm{span}(v_1, \ldots, v_N)\) の次元ごとに数えることを考えると、次が成り立ちます：

\[b_n = \sum_{k=0}^n \binom{\mathbf{n}}{\mathbf{k}}_q a_k\]

この \(a,b\) の関係は、\(q\)-二項係数を \(q\)-階乗を用いて表せば、

\[\frac{b_n}{[\mathbf{n}]_q!} = \sum_{k=0}^{n} \frac{a_k}{[\mathbf{k}]_q!}\cdot \frac{1}{[\mathbf{n-k}]_q!}\]

と書けるので、形式的べき級数除算を用いれば \((b_0, \ldots, b_N)\) から \((a_0, \ldots, a_N)\) を \(O(N\log N)\) 時間で復元できます（\(q\)-二項係数に対する反転公式を用いて、畳み込み 1 回でこれを行うこともできます）。

---

[2]

\(b_n\) の計算式は以下の通りです：

\[b_n = (2^n-0)(2^n-1)(2^n-2)\cdots (2^n-N+1)\]

これを \(0\leq n\leq N\) すべてで計算する方法を説明します。

\(b_n\) は、多項式 \((x-0)(x-1)\cdots (x-N+1)\) に \(x=2^n\) を代入したものです。したがって、

(1)： \(f(x) = (x-0)(x-1)\cdots (x-N+1)\) を展開する

(2)： 上の \(f\) に \(x=2^n\) （\(0\leq n\leq N\)）を代入した値を求める

が行えればよいです。

(1) は \(1\) 次式 \(N\) 個の総積で、分割統治と FFT を用いて \(O(N\log^2N)\) 時間で求められることがよく知られていると思います。

参考： https://judge.yosupo.jp/problem/product_of_polynomial_sequence

この部分は式の特殊性を用いるとさらに高速化することもできて、分割統治・FFT と polynomial taylor shift を組み合わせることで \(O(N\log N)\) 時間で計算することもできます

参考：https://judge.yosupo.jp/problem/stirling_number_of_the_first_kind

(2) は \(N\) 次式を \(N+1\) 点で多点評価する問題で、これも \(O(N\log^2N)\) 時間で行えることが有名だと思います。

参考：https://judge.yosupo.jp/problem/multipoint_evaluation

評価点が等比数列であることを利用して \(O(N\log N)\) 時間でこれを行うこともできます（なお、通常の多点評価と比べても、理屈も実装もかなり簡潔です）。

参考：https://noshi91.github.io/algorithm-encyclopedia/chirp-z-transform#noredirect

以上により、\(b_0, \ldots, b_N\) の計算が全体で \(O(N\log N)\) 時間で行えます。[1] で述べたことより、\(a_0, \ldots, a_N\) の計算が全体で \(O(N\log N)\) 時間で行えます。

---

[3]

\(a_0, \ldots, a_N\) が求まりました。これを利用して答えを求めましょう。\(a_n\) の答への寄与を考えると、次を求めることに帰着されます。

• \(\{0, 1, \ldots, 2^B-1\}\) の \(n\) 次元部分空間のうちで、\(1\) を含むものの割合を計算せよ

\(0\) 以外の要素がすべて対称的であることを考えると、この割合は \((2^n-1)/(2^B-1)\) です。したがって、

\[\sum_{n} a_n\cdot \binom{\mathbf{B}}{\mathbf{n}}_q\cdot \frac{2^n-1}{2^B-1}\cdot \]

が求めるものです。

以上により、\(O(N+B)\) 時間の前計算のもと \(O(N\log N)\) 時間で答を求めることができます。