洛谷P4933 大师

首先定义状态，dp[i][j]表示考虑到第i个数字时，公差为j的方案数.

对于每一个位置i，枚举它的上一个位置k，可得转移方程:

dp[i][h[i]-h[k]]+=dp[k][h[i]-h[k]]+1;

#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<algorithm> 
#include<string.h>
#include<iostream>
#include<queue>
#include<math.h>
#include<string>
#include<map>
#include<functional>
#include<vector>


#define inf 0x3f3f3f3f
#define mod 998244353

#define M 20002

using namespace std;


int h[1005];

int dp[1005][M*2];//考虑到第i个数字，公差为j的等差数列的个数
int n;

long long ans;
int main(void)
{
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &h[i]);
	}

	for (int i = 1; i <= n; i++)
	{
		ans++;
		for (int j = i - 1; j >= 1; j--)
		{
			dp[i][h[i] - h[j] + M] += dp[j][h[i] - h[j] + M] + 1;
			dp[i][h[i] - h[j] + M] %= mod;

			ans += dp[j][h[i] - h[j] + M]+1;
			ans %= mod;

		}
	}
	printf("%lld\n", ans);

	system("pause");
	return 0;
}