\(1\) 点解法

実際に、手元で適当な数列に対して指定された操作を行うと、観察から以下のことが分かります。

• \(N \le 2^i\) を満たす最小の \(i\) を \(d\) とする。長さ \(N\) の数列に対して、 \(2^d\) 回操作を行うと、操作を行う前の数列に戻る。

この事実は正しいです。証明は満点解法の部分で説明します。

よって \(N \le 2^i\) を満たす最小の \(i\) を \(d\) とすると、 \(K\) を \(2^d\) で割った余りの回数だけ操作を行えばよいことが分かります。

以上よりこの問題を \(\mathrm{O}(N2^d)\) 時間で解くことができます。 \(\mathrm{O}(d)=\mathrm{O}(\log N)\) なので \(\mathrm{O}(N 2^d ) = \mathrm{O}(N^2)\) より、 \(N \le 1000\) のもとでは十分高速です。

満点解法

以下 0-indexed で考えます。

まず、 XOR ではなく足し算で考えます。 \(A\) の母関数を \(f(x) = A_0 + A_1x + \dots + A_{N - 1}x^{N - 1}\) とおきます。また、 \(A\) に対して \(K\) 回累積和をとった数列を \(S\) とおきます。

ここで \(A\) の累積和の母関数は \(\frac{f(x)}{1 - x}\) となるため、 \(S\) の母関数は \(\frac{f(x)}{(1 - x)^K}\) になります。

負の二項係数 \(\frac{1}{(1 - x)^\alpha}\) について、

\[ \frac{1}{(1 - x)^\alpha} = \sum_{k = 0}^\infty \binom{\alpha + k - 1}{k} x^k = \sum_{k = 0}^\infty \binom{\alpha + k - 1}{\alpha - 1} x^k \]

が成り立ちます。参考 ： maspy さんの記事

ここで、

\[ S_i = [x^K] \frac{f(x)}{(1 - x)^K} \]

であるため、

\[ S_i = \sum_{j \le i} \binom{K + (i - j) - 1}{K - 1} A_j \]

となります。

今回は XOR なので各 bit について考えればよいです。そのため \(A\) の要素が \(0\) または \(1\) のみであるとして考えます。 この場合、 XOR と足し算は \(\mod{2}\) で一致するため、先ほどの議論を \(\mod{2}\) で考えればよいです。

\(A\) に対して \(K\) 回操作を行った数列を \(C\) とすると、

\[ C_i \equiv \sum_{j \le i} \binom{K + (i - j) - 1}{K - 1} A_j \pmod{2} \]

となります。 ここで、以下のように数列 \(B\) を定めます。

\[ B_i = \binom{i+(K-1)}{K-1} \]

すると、 \(C_i\) は以下のように表せます。

\[ C_i \equiv \sum_{j + k = i} A_j \cdot B_k \pmod{2} \]

これは畳み込みの式に一致するため、 \(B\) が求まれば高速フーリエ変換を利用することで \(O(N\log{N})\) 時間で解くことができます。

\(B\) の求め方について解説します。

\(B\) は \(\mod{2}\) で求まれば良いです。

Lucas の定理より、

\[ \binom{m}{n} \equiv \prod_{i = 0}^d \binom{m_i}{n_i} \pmod{2} \]

が成り立ちます。ただし、

\(m = m_d m_{d - 1} \cdots m_1 {}_{(2)}\)

\(n = n_d n_{d - 1} \cdots n_1 {}_{(2)}\)

です。

そのため、 \(B_i\) は \(m_i = 0\) かつ \(n_i = 1\) となるような \(i\) が存在するとき \(0\) に、そうでないときに \(1\) になることが分かります。 よって、

\[ B_i \equiv \begin{cases} 1 & ((i + K - 1)\mathrm{AND}(K - 1) = K - 1) \\ 0 & (\text{otherwise}) \end{cases} \pmod{2} \]

となります。ただし、 \(\mathrm{AND}\) は bit 毎の AND 演算を指します。

またこのことから、 \(K - 1\) の bit のうち、 \(i\) のとり得る最上位の bit より上のものは \(B\) の構築において無関係であることが分かります。 そのため、

• \(N \le 2^i\) を満たす最小の \(i\) を \(d\) とすると、 長さ \(N\) の数列に対して、 \(2^d\) 回操作を行うと、操作を行う前の数列に戻る。

という事実は正しいことが分かります。

本問題では各 bit に対して畳み込みを行う必要があるため、全体で \(O(N\log{N}\log{\max (A)})\) 時間で解くことができます。

クレジット

原案： Jinapetto, powell

解法： nu50218, null0124

問題準備・解説： Jinapetto

レビュー： null0124

テスター： QCFium

校正： nu50218