Bob の \(P\) についてわかっている情報は常に以下のようになります。

ある整数 \(1\leq a \leq N\) が存在して、

• \(i\lt a\) について、 \(P_{i}\) が何かがわかっている。
• \(i=a\) について、 \(P_{i}\) としてあり得ないものがいくつかわかっている。
• \(a\lt i\) について、 \(P_{i}\) の情報は何も知らない。

よって、 Bob のとる最適な戦略は上記の \(a\) を用いて以下のようになります。

• \(i\lt a\) について、 \(Q_{i}=P_{i}\)
• \(i=a\) について、 \(P_{i}\) としてあり得るものからひとつ選んで \(x\) として、\(Q_{i}=x\) とする。
• \(a\lt i\) について、 \(Q_{i}\) を適当に決める。

この戦略で最小な \(i\) として \(a\) が帰ってくる回数が \(b\) 回である確率は \(0\leq b\lt N-a\) ならば \(\frac{1}{N+1-a}\) で、 \(a\) について独立です。

よって、 \([x^{a}]f(x):=(a+1) 回目の質問でコーラがもらえる\) と定義された多項式 \(f(x)\) は以下が成り立ちます。

\[ f(x)=\prod_{i=1}^{N}(\frac{1}{i}\sum_{j=0}^{i-1}x^{j})=\frac{1}{N!}\prod_{i=1}^{N}\frac{1-x^{i}}{1-x}=\frac{1}{N!}\frac{1}{(1-x)^{N}}\prod_{i=1}^{N}(1-x^{i})\]

ここから先は形式的冪級数を用います。

\(\displaystyle\sum_{i=0}^{M-1}[x^{i}]f(x)=[x^{M-1}]\left(\frac{f(x)}{1-x}\right)\) より、 任意の \(0\leq i\lt M\) について、 \([x^{i}] \left(\frac{1}{(1-x)^{N+1}}\right)\) と \([x^{i}]\displaystyle\prod_{j=1}^{N}(1-x^{j})\) について求めることができれば良いです。

\([x^{i}] \left(\frac{1}{(1-x)^{N+1}}\right)=\dbinom{N+i}{N}\) であるので、前計算 \(O(N+M)\) で \(O(1)\) で求めることができます。

\(\displaystyle\prod_{j=1}^{N}(1-x^{j})\) について、求め方を \(2\) 通り紹介します。

[1] 部分点方針

\(\displaystyle\prod_{j=1}^{N}(1-x^{j})=\text{exp}(\sum_{j}^{N}\text{log}(1-x^{j}))\) が成り立ちます。 \(\log(1-x^{i})=-\displaystyle\sum_{n=1}^{\infty} \frac{x^{in}}{n}\) より、各 \(i\) について、前 \(M\) 項を求めるのに \(O(\frac{N}{i})\) かかるので、\(\displaystyle\sum_{j}^{N}\text{log}(1-x^{j})\) の前 \(M\) 項を求めるのにかかる計算量は、調和級数より \(O(N\log(M))\) となります。

\(\text{exp}\) は \(O(M\log(M))\) で計算できるので、この方針で部分点を取ることができます。

参考 形式的冪級数の log exp について https://maspypy.com/多項式・形式的べき級数-高速に計算できるもの#toc3

部分点実装例 https://atcoder.jp/contests/ttpc2023/submissions/45504947

[2] 満点方針

\(0\leq i\leq M\leq N\) について以下が成り立ちます。

\[[x^{i}]\prod_{j=1}^{N}(1-x^{j})=[x^{i}]\prod_{j=1}^{\infty}(1-x^{j})\]

よって、オイラーの五角数の定理を用いれば、 \(O(\sqrt{M})\) の前計算をすることで、 \([x^{i}]\displaystyle\prod_{j=1}^{N}(1-x^{j})\) が \(O(1)\) で求まります。

参考 オイラーの五角数の定理について https://ja.wikipedia.org/wiki/オイラーの五角数定理

満点実装例 https://atcoder.jp/contests/ttpc2023/submissions/45504878