未知のカードは互いに等価であることから、次の戦略が最適になります。

• \(x\) が書かれたカードが既知のとき、そのカードを表にする
• そうでないとき、未知のカードのうち最も左のものを表にする

この戦略の下で、数 \(i\) が書かれたカードが表にされる回数は、 \(1,2,\ldots,i\) のカードの中で \(i\) が最も右にあるとき \(1\) 回、そうでないとき \(2\) 回です。

カードをランダムに並べたとき、「\(1,2,\ldots,i\) のうち最も右のカード」は当然ランダムなので、それが \(i\) である確率は \(\frac{1}{i}\) です。

よって求める答えは \(\displaystyle [x^K]\prod_{i=1}^{N}\left(\frac{1}{i}x+\frac{i-1}{i}x^2\right)\) となり、これはよく知られた手法により \(O(N(\log N)^2)\) になります（解説略）