\(f(A)\) は \(A_i(1 \le i \le N-1)\) の \(\max\) top 2 の積 + top 2 のうち後ろにあるものより後ろにある \(\max\) と等しいことが証明できます。(タイブレークは \(i\) の昇順とします。)

この事実を認めた上で数え上げを行います。top 2 の値を \(x,y\) としましょう。すると、\(A\) として条件を満たすのは以下の形として表されるのみです。

• \(1\) 以上 \(\min(x-1,y-1)\) 以下の値任意個
• \(x\)
• \(1\) 以上 \(\min(x,y-1)\) 以下の値任意個
• \(y\)
• \(1\) 以上 \(\min(x,y,K-xy)\) 以下の値任意個
• \(1\) 以上 \(K-xy\) 以下の値 \(1\) 個

この形の個数は Bostan-Mori 法等で \(\mathrm{O}(\log N)\) で求めることが出来ます。\((x,y)\) の個数は \(\mathrm{O}(K \log K)\) で抑えられるため、計算量は \(\mathrm{O}(K \log K \log N)\) となります。

上記で使った事実の証明をします。top 2 の要素を \(A_i,A_j\) とし、\(A_j\) より後ろにあるもののうち最大値を取るものの一つを \(A_k\) とします。そして、よりよい解として \(A_x A_y + A_z\) が取れたとしましょう。

• $j \le y$ のとき
$A_iA_j \le A_xA_y$ かつ $A_k \le A_z$ が言えるため矛盾します。
• $y < j$ のとき
$j < z$ とすると $A_iA_j \le A_xA_y$ かつ $A_k \le A_z$ が言えるため矛盾します。また、$A_j$ は $A_1,A_2,\dots,A_j$ の中で $A_i$ を除くと最大のため、$z = i,j$ のどちらかであることが分かります。
• $z = i$ のとき
$A_x,A_y < \min(A_i,A_j)$ より、$A_xA_y \le (A_i-1)(A_j-1) = A_iA_j - A_i - A_j + 1 \le A_iA_j - A_i$ となるため、$A_xA_y + A_z \le A_iA_j - A_i + A_i \le A_iA_j < A_iA_j + A_k$ となり矛盾します。
• $z = j$ のとき
$A_x,A_y < \min(A_i,A_j-1)$ より、$A_xA_y \le A_i(A_j-1) = A_iA_j - A_j$ となるため、$A_xA_y + A_z \le A_iA_j - A_j + A_j \le A_iA_j < A_iA_j + A_k$ となり矛盾します。

よって示されました。