原题链接： 大师

题意：给定一个长度为 $n$ 的整数序列，每个元素的值在 $[1, 20000]$ 内，求有多少个不同的子序列可以构成等差数列。$n \leq 1000$。

不会做才来写题解加深一下印象qwq

假定状态 $f[i][j]$ 为以第 $i$ 个数结尾，公差为 $j$ 的等差数列的方案数
大概可以想到转移方程为 $f[i][j] = \sum_{k = 1}^{i - 1}$ if(h[i] - h[k] == j) $f[k][h[i] - h[k]]$，时间复杂度 $O({n}^{2}m)$

由于两个数可以唯一确定一个公差，可以枚举第 $i$ 个数前面的每一个数，计算公差为 $d = h[i] - h[j]$

以第 $j$ 个数结尾的公差为$d$ 的等差数列，都可以把第$j$个数替换成第$i$个数，并且第 $i$个数和第 $j$ 个数也能组成一个长度为 $2$ 公差为 $d$ 的等差数列，得状态转移方程 $f[i][d] = f[i][d] + f[j][d] + 1$
同时新增 $f[j][d] + 1$ 个可以形成等差数列的子序列，累加到答案里

最后由于可能有公差为负数的情况，所以把数组的第二维开两倍，整体向右移动 $20000$ 即可

时间复杂度 $O({n}^{2})$

#include<cstdio>
#include<cstring>

const int N = 1010, M = 20010, mod = 998244353;

int h[N], f[N][M * 2];      //  f[i][j]表示以i结尾，公差为j - M的方案数
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)  scanf("%d", &h[i]);

    int res = 0;
    for(int i = 1; i <= n; i ++)
    {
        res ++;
        for(int j = 1; j < i; j ++)
        {
            int d = h[i] - h[j] + M;
            f[i][d] = (f[i][d] + f[j][d] + 1) % mod;
            res = (res + f[j][d] + 1) % mod;
        }
    }
    printf("%d", res % mod);
    return 0;
}