注：公式解説の \(O(N^3)\) 解法と本質的には等価です

\(\mathrm{dp}[i][k][d]\) = 長さ\(k(\geq2)\)の等差数列で、公差が \(d\) で、末尾が \(A_i\) のものの個数

とします。求める答えは \(k\) ごとに \(\sum_{i,d}\mathrm{dp}[i][k][d]\) となることから、このDPテーブルが全て埋められれば \(\tilde{O}(N^3)\) で答えを求めることができます。（\(i,k\) ごとに、\(\mathrm{dp}[i][k][d]\neq 0\) となる \(d\) は \(O(N)\) 個しかないことに注意してください）

\(\mathrm{dp}[*][2][*]\) は全探索により明らかに \(\tilde{O}(N^2)\) で全て求めることができます。

\(k>2\) のとき \(\mathrm{dp}[i][k][*]\) は、末尾から \(2\) 番目の要素がどこから来たかを考えるもらうDPにより

for j in 1 to i-1:
  dp[i][k][A[i]-A[j]] += dp[j][k-1][A[i]-A[j]]

と \(i\) の昇順に計算することができます。

\(i,k\) ごとに \(dp[i][k][*]\) を \(\tilde{O}(N)\) で計算できることから、DPテーブル全体を求めることは \(\tilde{O}(N^3)\) ででき、元の問題は \(\tilde{O}(N^3)\) で解けました。

実装例(Python)