题解 P4933 【大师】

# 这题v在long long以内也是可以做的 这里提出一种$n^2logn$的有别于官方题解的做法 首先发现一个性质：**每个点要作为等差数列的中间部分，则公差最多只有n种** 所以我们可以对此下手 QAQ 设$t[i].g[j]$表示高度为i的塔，前面接上公差为j的等差数列有多少种方案，num记录有多少高度为i的塔 于是转移就很显然了，往后加上高度为k的塔的时候，枚举前面的塔是i，有两种方式贡献答案： - 直接把i作为等差数列开头（$ans+=num$） - 把i作为等差数列中间（$ans+=t[i].g[k-i]$） 同时把新增的答案更新到k的状态上去即可 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<map> #include<algorithm> using namespace std; const int N=1010,mod=998244353; struct Node{map<int,int> g;int num;}t[N]; int n,h[N],B[N],rk[N],up,ans; map<int,int> Map; void add(int &a,int b) {a+=b;if(a>=mod) a-=mod;} int main() { cin>>n;ans=n; for(int i=1;i<=n;i++) cin>>h[i],B[i]=h[i]; sort(B+1,B+n+1); up=unique(B+1,B+n+1)-B-1; for(int i=1;i<=up;i++) Map[B[i]]=i,rk[i]=B[i]; for(int i=1;i<=n;i++) h[i]=Map[h[i]]; for(int i=1;i<=n;i++) { for(int j=1;j<=up;j++) { int d=rk[h[i]]-rk[j],res=t[j].num; if(t[j].g.find(d)!=t[j].g.end()) add(res,t[j].g[d]); if(!res) continue; add(ans,res); add(t[h[i]].g[d],res); } t[h[i]].num++; } return cout<<ans<<endl,0; } ``` 广告：https://www.cnblogs.com/xzyxzy