这道题加强了我对dp和等差数列的认识。。。

暴力做法是我第一个想出来的，但是可能实现起来还比满分做法复杂。。。

暴力能拿30pts。

暴力太难做的就要想想dp！也许用dp，问题就变得很容易求的了。

这里有两种思路。

法一

用dp[i][j]表示等差数列最后第二项的值为\(h[i]\)，最后一项\(h[j]\)的方案数。

特例：当\(i=0\)时，表示等差数列只有一个数。

显然我们可以在前面枚举一个\(k\)，一旦差值相等，直接从\(dp[k][i]\)转移过来。

这样的枚举是\(O(n^3)\)的，但是它的常数极小。比\(O(n^2)\)慢不到哪里去。

要学会这样的“暴力”dp。这样的做法在我之前的一道状压dp有见过。

法二

用dp[i][j]表示等差数列从\([1,i]\)，公差为\(j\)的方案数。

然后你可以直接枚举\(i\)前面的数，看看是不是满足公差，如果是，直接转移。

这个的复杂度是\(O(n^2)\)的。

代码：

#include
    
     #define ll long longconst int maxn = 1005;const int MOD = 998244353;ll h[maxn], n;ll dp[maxn][maxn];int main(){    scanf("%d", &n);    for(int i = 1; i <= n; i++) scanf("%d", &h[i]);    for(int i = 1; i <= n; i++)    {        dp[0][i] = 1;    }    ll ans = 0;    for(int i = 2; i <= n; i++)    {        for(int j = 1; j < i; j++)        {            dp[j][i] = dp[0][j] % MOD;            for(int k = 1; k < j; k++)            {                if(h[j] - h[k] == h[i] - h[j]) dp[j][i] = (dp[j][i] + dp[k][j]) % MOD;            }        }    }        for(int i = 0; i <= n; i++)    {        for(int j = 1; j <= n; j++)        {            ans = (ans + dp[i][j]) % MOD;        }    }    printf("%lld\n", ans);    return 0;}
    

#include
    
     #define ll long longconst int maxn = 1005;const int MOD = 998244353;ll h[maxn], n;ll dp[maxn][40005];int main(){    scanf("%lld", &n);    for(int i = 1; i <= n; i++) scanf("%lld", &h[i]);        ll ans = 0;    for(int i = 1; i <= n; i++)    {        for(int j = 1; j < i; j++)        {            int delta = h[i] - h[j];            dp[i][delta + 20000] = (dp[i][delta + 20000] + dp[j][delta + 20000] + 1) % MOD;                        ans = (ans + dp[j][delta + 20000] + 1) % MOD;        }    }    printf("%lld\n", ans + n);    return 0;}