\(S_1,...,S_N\) に対する答えを \(f(S_1,...,S_N)\) としましょう。

• \(S_N\) が AND のとき、\(y_{N-1}\) と \(x_N\) はともに\(\text{True}\) でなければなりません。よって \(f(S_1,...,S_N)=f(S_1,...,S_{N-1})\) です。
• \(S_N\) がOR のとき、\(x_N\) が \(\text{True}\) なら \(y_{N-1}\)は何でもよく、\(x_N\)が \(\text{False}\) なら \(y_{N-1}\) は \(\text{True}\) でなければなりません。よって \(f(S_1,...,S_N)=2^N+f(S_1,...,S_{N-1})\) です。

以上により \(O(N)\) でこの問題が解けました。