P4933 大师

题目大意

给定序列 $h_1,dots,h_n$。统计所有长度至少为 1 的等差子序列的个数（对 $998244353$ 取模）。

AC代码

具体思路与该题解一致

https://www.luogu.com.cn/article/hrn3rj07

#include <iostream>
#include <vector>
using namespace std;
const int mod=998244353,N=1010,MAXR=4e4+10,R=4e4;  // random
int n,h[N],dp[N][MAXR*2],ans;     // dp里存到这第i个塔时有每种公差有多少种方案  这个dp数组大约77MB 题目限制是500MB
// 还需要介绍的是 如 1 2 3 4 这个等差数列 在这题中有4+3+2+1种（单个+2个+3个+4个）
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>h[i];
    }
    for(int i=1;i<=n;i++) {
        ans++;                  // 这里ans统计单个
        for(int j=i-1;j>=1;j--) {
            dp[i][h[i]-h[j]+R]+=dp[j][h[i]-h[j]+R]+1;    // 这里dp统计多个（>=2）所以个数为1
            dp[i][h[i]-h[j]+R]%=mod;
            ans+=dp[j][h[i]-h[j]+R]+1;
            ans%=mod;
        }
    }
    ans%=mod;
    cout<<ans<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/183896339

心路历程（WA，TLE，MLE……）