P4933 大师（DP)

题意：给定序列求所有子序列中为等差数列的个数。(序列长度为1，2被认为是等差序列，空序列不是等差序列)。

思路：很巧妙的 $dp$ ,因为 $a[i]\leq 2e4$ ,数字较小。所以考虑设 $dp[i][j]$ 表示以下标 $i$ 的数字结尾公差为 $j$ 的等差序列个数。因为公差可能为负，所以整体向右移动 $2e4$ 位。

状态转移方程： $dp[i][a[i]-a[j]+2e4]+=dp[j][a[i]-a[j]+2e4]+1$ .

这个 $1$ 是当 $a[j],a[i]$ 两个数组成的等差序列。因为开始一个数的等差序列我们可以预处理就是 $n$ 了。所以 $dp[i][j]$ 里面是不含一个数等差序列，所以递推时要加上1.

还有一个注意的问题，因为我们不知道每个等差序列的公差是多少，所以我们在递推的时候一边递推，一边要加上贡献。

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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=4e4+5,mod=998244353;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
inline void read(int &x){ 
    x=0;int w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    for(;ch>='0'&&ch<='9';ch=getchar())
        x=(x<<3)+(x<<1)+(ch&15);
    x*=w; 
}
int h[N],dp[N][M],n;
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(h[i]);
    ll ans=0;
    int p=2e4; 
    for(int i=1;i<=n;i++){
        ans++;
        for(int j=i-1;j>=1;j--){
            dp[i][h[i]-h[j]+p]=(dp[i][h[i]-h[j]+p]+dp[j][h[i]-h[j]+p]+1)%mod;
            ans=(ans+dp[j][h[i]-h[j]+p]+1)%mod;
        }
    }
    printf("%lld\n",ans);
    return 0;
}