部分点 1 $(N \le 2000,M \le 10,Q = 1)$

\(dp[i][j] = i\) 回目まで操作して黒い箱に入っているボールの状態が \(j\) であるという bit DP でこの問題を解くことが出来ます。計算量は \(\mathrm{O}(N2^MMQ)\) です。

部分点 2 $(Q = 1)$

ボール \(M,M-1,\dots,1\) の順に挙動を決めていきます。ボール \(k\) の条件として、ほとんどの場合はボール \(k\) が黒い箱に存在することの出来る極大な区間 \([l,r]\) の中でボール \(k\) は偶数回選ばれていることとなります。ここでほとんどの場合というのは、もしその区間が \(N\) 回目の操作後も含むならば奇数回選ばれていても問題ないからです。

ここで、それぞれの極大な区間 \([l,r]\) について後何回操作が残っているかを持って動的計画法をすることにします。遷移としては、まず \([l,r]\) においてボール \(k+1,k+2,\dots,M\) の挙動を決めたとき後何回操作が残っているかを計算します。それから、もしその区間が全体の右端を含まない場合は偶数個使う遷移を行います。つまり、列 \(f_0,f_1,\dots,f_d\) に対して列 \(g_i = \sum_{j \le i,j = i \bmod 2} f_j \binom{j}{i}\) を計算出来ればよいです。これは畳み込みを用いて \(\mathrm{O}(d\log d)\) で計算出来ます。

以下の図も参考にしてください。これは \(N=6,M=3,A=(1,3,2,2,3,1)\) の時の図です。例えば、下から \(3\) 段目においてボール \(3\) が黒い箱に存在することの出来る極大な区間 \([2,3]\) を考えます。両方ボール \(3\) に充てるか充てないかでそれぞれ残り操作回数が \(0,2\) なので \(x^2 + 1\) を持っています。

下から \(2\) 段目においてボール \(2\) が黒い箱に存在することの出来る極大な区間 \([2,6]\) を考えます。\([2,6]\) においてボール \(3\) の挙動を決めたときの残り操作回数の母関数は \((x^2+1) x (x^2 + 1) = x^5 + 2x^3 + x\) となります。ここから偶数個使う遷移をすると \(x^5 + 12x^3 + 12x\) となります。

下から \(1\) 段目の極大な区間 \([1,7]\) については、右端を持っているため操作回数が奇数回でもよいことに注意してください。

上記を実装することで、この問題を \(\mathrm{O}(Q N M \log N \log \left(\frac{N}{M} \right))\) で解くことが出来ます。

満点

偶数個使う遷移について考えます。母関数 \(f(x)\) から任意個使う場合、\(g(x) = f(x+1)\) とすればよいです。ここから偶数個使う遷移にするには、\(g(x) = \frac{f(x+1)+f(x-1)}{2}\) とすればよいです。ですが、このままだと計算量は変わりません。

さて、答えは一番下の段の遷移後の母関数 \(f(x)\) に対する \(f(1)\) です。よって、下から \(k\) 段目の母関数に対して \(f(2-k),f(3-k),\dots,f(k)\) の値のみを持てば遷移が可能です。これで \(1\) 区間の持つ情報量を \(\mathrm{O}(M)\) 個に抑えることが出来ました。

クエリを処理することを考えます。\(k\) 段目の区間は \(k+1\) 段目の区間に依存しているため、更新する際は上の列から更新する必要があります。このとき、適切に極大な区間を扱うことでクエリは \(\mathrm{O}(M)\) 個の区間の削除と追加を行うことに帰着されます。まず、前準備として \(1 \le k \le M,2-k \le l \le k\) を満たす \((k,v)\) に対して下から \(k\) 段目の区間に対する \(f(v)\) を管理するセグ木を持ちます。(演算は積とします。)

追加について考えます。\(k\) 段目の区間 \([l,r]\) を追加するとき、\(k+1\) 段目のセグ木全ての \([l,r]\) の値を求め、\(g(x) = \frac{f(x+1)+f(x-1)}{2}\) を用いて遷移をし、\(k\) 段目のセグ木を更新すればよいです。削除についてはただ \(k\) 段目のセグ木の \(f(v)\) を削除すればよいです。よって、\(1\) クエリあたり \(\mathrm{O}(M^2 \log N)\) で処理することが出来ます。

上記によって、この問題を \(\mathrm{O}((N + Q)M^2 \log N)\) で解くことが出来ます。