【题解】洛谷 P4933 —— 等差子序列计数（DP + 哈希表）

思路#

把“等差子序列”按 最后一项 和 公差 分类。
逐个枚举位置 $i$ 作为最后一项，用哈希表维护：
“以 $a_i$ 结尾、某个公差 $d$ 的等差子序列有多少个”。

状态#

设输入数组为 $a[0..n-1]$ , 约定 $a[i]$ 为 $a_i$ 。

定义状态：
$dp[i][d]$ 表示：以 $a_i$ 结尾、公差为 $d$ 的等差子序列个数（长度 ≥ 2）。

转移方程#

固定 $i$，枚举所有 $j < i$，令 $d = a_i - a_j$

此时会产生两类贡献：

1. 新长度为 2 的等差子序列：$(a_j, a_i)$
   贡献 $+1$

2. 把所有以 $a_j$ 结尾、公差同为 $d$ 的等差子序列接上 $a_i$
   贡献 $+dp[j][d]$

因此：

$dp[i][d] += dp[j][d] + 1$

完整状态转移方程如下：

同时，题目要求统计所有等差子序列总数。
每次转移新增了 $dp[j][d] + 1$ 个合法子序列，所以直接累加到答案即可。

外层 $i$，内层 $j$：时间复杂度 $O(n^2)$
使用 哈希表(unordered_map) 按需存储不同公差，减少内存使用。

代码实现#

下面代码按照上述 DP 直接实现：
$dp[i]$ 是一个哈希表：key 为公差，value 为方案数。
每次枚举 $(j, i)$ 更新 $dp[i][d]$，并把新增数量累加到 $cnt$。

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4
const i64 Z = 998244353;
5

6
int main(){
7
    i64 n;cin>>n;
8
    vector<i64> a(n);for(i64& x:a)cin>>x;
9

10
    // dp[i][d]：以a[i]结尾、公差为 d 的（长度>=2）等差子序列数量
11
    vector<unordered_map<i64,i64>> dp(n);
12

13
    i64 cnt = 0;
14
    for(int i=0;i<n;++i){
15
        cnt++;
16
        for(int j=i-1;j>=0;--j){
17
            dp[i][a[i]-a[j]] += dp[j][a[i]-a[j]]+1;
18
            dp[i][a[i]-a[j]] %= Z;
19
            cnt += dp[j][a[i]-a[j]]+1;
20
            cnt %= Z;
21
        }
22
    }
23
    cout<<cnt<<endl;
24
    return 0;
25
}