[1]問題の言い換え

この問題は、以下のように言い換えることができます。

平面上に円があり、円上に \(X+Y+Z+3\) 個の点がある。点には順番に \(0\) から \(X+Y+Z+2\) の番号がついている。

点 \(0,X+1,X+Y+2\) に人が立っている。ここで以下の操作を \(N\) 回行う。

• 人を \(1\) 人選ぶ。選んだ人のいる点の番号を \(i\) とする。選んだ人を点 \(i+1 \bmod X+Y+Z+3\) に移動させる。このとき、人が重なってはならない。

操作を \(N\) 回行う方法の個数 \(\bmod\ 2\) を求めよ。

以降、この問題を解くこととします。また、\(M=X+Y+Z+3\) とおきます。そして、はじめ点 \(0\) にいる人を人 \(1\)、はじめ点 \(X+1\) にいる人を人 \(2\)、はじめ点 \(X+Y+2\) にいる人を人 \(3\) と言うこととします。

---

[2]逆から見る

ここで、操作を逆から見ることにします。つまり、始めの人の状態は人 \(1,2,3\) がこの順で並んでいれば各々がどこにいてもいいが、最終的に人 \(1\) が点 \(0\) に、人 \(2\) が点 \(X+1\) に、人 \(3\) が \(X+Y+2\) にいるような方法の個数を求めることにします。このようにしても答えは変わりません。

---

[3]動的計画法の利用

上記の問題は、以下の動的計画法を用いることによって解くことができます。

\(\mathrm{dp}[i][j][k]:=i\) 回操作を行ったとき、「人 \(2\) のいる点の座標 \(-\) 人 \(1\) のいる点の座標 \(= j \bmod\ M\)」かつ「人 \(3\) のいる点の座標 \(-\) 人 \(2\) のいる点の座標 \(= k \bmod\ M\)」かつまだ誰も重なってないような方法の個数 \(\bmod\ 2\)

遷移は以下のように行います。

\(\begin{cases} \mathrm{dp}[i][j][k]=\mathrm{dp}[i-1][j-1][k]+\mathrm{dp}[i-1][j+1][k-1] + \mathrm{dp}[i-1][j][k+1](1 \le i \le N,1 \le j,k \le M-2,j+k \le M-1) \end{cases}\)

初期化は、\(\mathrm{dp}[0][j][k]=1\) です。解は \(\mathrm{dp}[N][X+1][Y+1]\) です。また、添え字の範囲外の値は全て \(0\) とします。

このままでは計算量が \(\mathrm{O}(NM^2)\) となってしまい到底間に合いません。

---

[4]鏡像法の利用

\(\mathrm{dp}[i]\) を切り取ると、以下のようになります。(\(M=5\))

\(\mathrm{dp}[i][1][1]\ \mathrm{dp}[i][1][2]\ \mathrm{dp}[i][1][3]\)

\(\mathrm{dp}[i][2][1]\ \mathrm{dp}[i][2][2]\)

\(\mathrm{dp}[i][3][1]\)

ここで、\(\mathrm{dp}[i]\) を拡張します。具体的には、\(j,k\) の範囲を \(1 \le j,k \le M-2,j+k \le M-1\) から \(0 \le j,k \le M-1\) に拡張します。

このとき、\(1 \le j,k \le M-2,j+k \le M-1\) を満たさない部分については以下のように定義します。

\(\begin{cases} \mathrm{dp}[i][j][k]=0(j=0\ \mathrm{or}\ k=0\ \mathrm{or}\ j+k=0 \bmod\ M) \\ \mathrm{dp}[i][j][k]=\mathrm{dp}[i][M-k][M-j](\mathrm{else}) \end{cases}\)

このとき、遷移を以下のように行うことができます。

\(\begin{cases} \mathrm{dp}[i][j][k]=\mathrm{dp}[i-1][j-1 \bmod M][k]+\mathrm{dp}[i-1][j+1 \bmod M][k-1 \bmod M] + \mathrm{dp}[i-1][j][k+1 \bmod M](1 \le i \le N,0 \le j,k \le M-1) \end{cases}\)

これは、\(\mathrm{dp}[i][j][k]=\mathrm{dp}[i][k][j]\) や \(\mathrm{dp}[i][j][k]=\mathrm{dp}[M-(j+k)][j]\) であることに注意すると証明可能です。

つまり、この遷移式は \(f_i(x,y)=\sum_{j=0}^{M-1} \sum_{k=0}^{M-1} \mathrm{dp}[i][j][k] x^jy^k\) としたとき、\(f_{i+1}(x,y)=f_i(x,y) \times \left(x + \frac{y}{x} + \frac{1}{y}\right) \bmod (x^M-1)(y^M-1)\) が成り立つということです。

ここで、\(\bmod\ 2\) で考えればよいため \(f_0(x,y) = \left(\sum_{j=0}^{M-1} \sum_{k=0}^{M-1} x^jy^k \right) + \left(\sum_{j=0}^{M-1} x^j \right) + \left(\sum_{k=0}^{M-1} y^k \right) + \left(\sum_{j=0}^{M-1} x^jy^{M-j} \right)\) としてよいことに注意してください。

解は \(f_N(x,y)\) の \(x^{X+1}y^{Y+1}\) の係数です。以降、\(f_0(x,y)\) のそれぞれの項に対して考えます。以下、全て \(\bmod (x^M-1)(y^M-1)\) で考えます。

• $\left(\sum_{j=0}^{M-1} \sum_{k=0}^{M-1} x^jy^k \right)$ は、$\left(x + \frac{y}{x} + \frac{1}{y}\right)^N$ の全ての項がかかるため、$\left(\sum_{j=0}^{M-1} \sum_{k=0}^{M-1} x^jy^k \right) \times \left(x + \frac{y}{x} + \frac{1}{y}\right)^N$ の $x^{X+1}y^{Y+1}$ の係数は $1$ です。
• $\left(\sum_{j=0}^{M-1} x^j \right)$ は、$x$ を無視してよいため、$\left(\sum_{j=0}^{M-1} x^j \right) \times \left(x + \frac{y}{x} + \frac{1}{y}\right)^N$ の $x^{X+1}y^{Y+1}$ の係数は $\left(1 + y + \frac{1}{y}\right)^N$ の $y^{Y+1}$ の係数に等しいです。
• $\left(\sum_{k=0}^{M-1} y^k \right)$ も同様に、$\left(x + \frac{1}{x} + 1\right)^N$ の $x^{X+1}$ の係数に等しいです。
• $\left(\sum_{j=0}^{M-1} x^jy^{M-j} \right)$ も同様に、$x,y$ の区別をする必要がないため $\left(x + 1 + \frac{1}{x}\right)^N$ の $x^{X+Y+2}$ の係数に等しいです。

よって、以下の問題を \(3\) 回解くことができれば元の問題を解くことができます。

$\left(x + 1 + \frac{1}{x}\right)^N \bmod (x^M-1)$ の $x^K$ の係数 $\bmod\ 2$を求めよ。

ここで、\((x + y)^{2^a} = x^{2^a} + y^{2^a} \bmod 2\) が成り立つので、\(N = 2^{A_1} + 2^{A_2} + 2^{A_3} + \dots + 2^{A_k}\) としたとき、\(\left(x + 1 + \frac{1}{x}\right)^N = \prod_{i=1}^{k} \left(x^{2^{A_i}} + 1 + x^{-2^{A_i}}\right)\) となります。ここで、\(k = \mathrm{O}(\log N)\) であることに注意してください。

---

[5]$\mathrm{O}(M\log N)$ 解法

\(\mathrm{dp}[i][j] = [x^j]\prod_{p=1}^{i} \left(x^{2^{A_p}} + 1 + x^{-2^{A_p}}\right)\) と定義された動的計画法をすることにより、\(\mathrm{O}(M \log N)\) で解くことができます。

---

[6]$\mathrm{O}\left(\frac{N\log N}{M}\right)$ 解法

全体に \(x^N\) をかけることにより、\(\prod_{i=1}^{k} \left(1+x^{2^{A_i}} + x^{2^{A_i+1}}\right)\) を考えます。

ここで、\(\bmod (x^M-1)\) を取るのではなく、\(x^{K+iM}\) かつ \(0 \le K +iM \le 2N\) を満たす整数 \(i\) に対する \(x^{K+iM}\) の係数の総和を取ることとします。

すると、この問題は以下の問題が解ければ解くことができます。

正整数 $N,X$ が与えられる。非負整数の組 $A,B,C$ のうち、$A+B+C=N$ かつ $A\ \mathrm{or}\ B\ \mathrm{or}\ C = N$ かつ $B+2C=X$ を満たすものの個数 $\bmod\ 2$ を求めよ。

これは、\(N\) の下位 bit から見て繰り上がりを管理する桁 dp をすることにより \(\mathrm{O}(\log N)\) で解くことができます。

この問題を \(\mathrm{O}\left(\frac{N}{M}\right)\) 回解くため、この解法の計算量は \(\mathrm{O}\left(\frac{N\log N}{M}\right)\) です。

---

[7]まとめ

よって

$\left(x + 1 + \frac{1}{x}\right)^N \bmod (x^M-1)$ の $x^K$ の係数 $\bmod\ 2$を求めよ。

を計算量の小さい方を選ぶことによって \(\mathrm{O}(\sqrt N \log N)\) で解くことができるため、元の問題も \(\mathrm{O}(\sqrt N \log N)\) で解くことができます。