题意

在一个有n个数的数列中找出所有等差数列，只有一个数的也算

思路

DP

首先设状态：$f[i][d]$表示在前i个数中有多少个公差为d的等差数列

状态转移方程：类似于LIS。对于每个以数列结尾 $i$，遍历 1 ~ i-1，若找到一个数 $j$ 与 $i$ 的差为 $d$ 的数，则公差为 $d$ 的数列长度+1

所以状态转移方程为：

代码

#include<bits/stdc++.h>
using namespace std;

const int MOD=998244353;
int n,h[1005],d;
map<int,int> f[1005];		//f[i][d]：在前i个数中有多少个公差为d的等差数列      
//公差d可能时负数，所以最好用map


int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			d=h[i]-h[j];
//			int s=f[i][d];
			f[i][d]+=(f[j][d]+1)%MOD;
			f[i][d]%=MOD;
//			printf("%d-%d=%d：%d->%d\t ",h[i],h[j],d,s,f[i][d]);	//输出dp过程
		}
//		cout<<'\n';
	}
	
	int ans=n;	//只有一个数也是等差数列
	for(int i=1;i<=n;i++){
		for(auto it=f[i].begin();it!=f[i].end();it++){
			ans+=it->second;
			ans%=MOD;
		}
	}
	
	cout<<ans;
	return 0;
}