長さ \(1\) の部分列はすべて等差数列であり，全部で \(N\) 個あります．これはあらかじめ数えておきます．以降，長さ \(2\) 以上の等差数列の数え上げを考えます．

\(O(N^4)\) 時間の解法

以下の状態を持つ DP を考えます．

\(\mathrm{dp}[i][j][l] \coloneqq\) 初項 \(A_i\)，第2項 \(A_j\)，長さ \(l\,(l \geq 2)\)であるような等差数列の個数

\(i\) の降順に見ていき，初項 \(A_i\) を固定します．第2項 \(A_j\,(i<j)\) と長さ \(l\) を全探索します． \(l=2\) の場合は \((A_i,A_j)\) が長さ \(2\) の等差数列なので， \(\mathrm{dp}[i][j][2]\) に \(1\) を足します． \(l\geq 3\) の場合は，更に第3項 \(A_k\,(j<k)\) を全探索します．\(A_k-A_j=A_j-A_i\) のとき，初項 \(A_i\)，第2項 \(A_j\)，長さ \(l\) の等差数列は，初項 \(A_j\)，第2項 \(A_k\)，長さ \(l-1\) の等差数列の先頭に \(A_i\) を追加したものとなっています．よって， \(\mathrm{dp}[i][j][l]\) に \(\mathrm{dp}[j][k][l-1]\) を足します．

状態数 \(O(N^3)\) に対して遷移が \(O(N)\) なので，全体で計算量は \(O(N^4)\) です．本問題の制約に対しては十分高速に動作します．

実装例 (PyPy)

\(O(N^3)\) 時間の解法

上の解法は更に高速化することができます．以下の状態を持つ DP を考えます．

\(\mathrm{dp}[i][l][d] \coloneqq\) 初項 \(A_i\)，長さ \(l\,(l \geq 2)\)，公差 \(d\) であるような等差数列の個数

\(i\) の降順に見ていき，初項 \(A_i\) を固定します．第2項 \(A_j\,(i<j)\) と長さ \(l\) を全探索します．このとき，公差は \(d\coloneqq A_j-A_i\) と定まります． \(l=2\) の場合は \((A_i,A_j)\) が長さ \(2\) の等差数列なので， \(\mathrm{dp}[i][2][d]\) に \(1\) を足します． \(l\geq 3\) の場合，初項 \(A_i\)，長さ \(l\)，公差 \(d\) の等差数列は，初項 \(A_j\)，長さ \(l-1\)，公差 \(d\) の等差数列の先頭に \(A_i\) を追加したものとなっています．よって， \(\mathrm{dp}[i][l][d]\) に \(\mathrm{dp}[j][l-1][d]\) を足します．

公差 \(d\) は \(10^9\) 程度の大きな値を取りうるため，\(d\) に関する添字は連想配列で持てばよいです．C++ で map を使用した場合，時間計算量は \(O(N^3\log N)\) となります．

または，各 \(i\) についてあり得る公差をあらかじめ列挙して座標圧縮しておけば，\(d\) に関する添字を配列で持つことができます．この場合，時間計算量は \(O(N^3)\) です．

実装例 (PyPy，座標圧縮)