P4933 大师

介绍一个较为好想的做法。

记为以第位为为首项，第为第二项的等差数列的个数。（）

则显然有（真的显然，做多了线性动态规划的人相信都能看出）

，其中

这样，状态，转移，总复杂度。

但有，为什么能过？

因为实际上,枚举的常数是，因为。

然后发现大概计算次数只有,

然后又有，就可以卡过此题。

(其实和正解的时间差的不大)

#include<iostream>
#include<cstring>
#include<cstdio>
#define p 998244353
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int maxn=1111;

int n,Ans,a[maxn],f[maxn][maxn];
int main(){
    scanf("%d",&n);
    rep(i,1,n)scanf("%d",&a[i]);
    rep(i,1,n-1)
    f[i][n]=1;
    dwn(j,n-1,2)
        dwn(i,j-1,1){
            f[i][j]=1;
            rep(k,j+1,n)
                if(a[k]-a[j]==a[j]-a[i])
                    f[i][j]=(f[i][j]+f[j][k])%p;
        }
    Ans=n;
    rep(i,1,n-1)
        rep(j,i+1,n)
            Ans=(Ans+f[i][j])%p;
    cout<<Ans;
    return 0;
}