P4933 大师 题解
博客园同步
原题链接
简要题意：
求一个数列中有多少个等差子序列。（子序列 不一定连续，子串 一定连续）
注：公差可以是负数。
算法一对于 30%30 \%30% 的数据，n≤20n \leq 20n≤20.
显然，枚举子序列，然后暴力验证。
时间复杂度：O(2n×n)O(2^n \times n)O(2n×n).
实际得分：30pts30pts30pts.
算法二对于 60%60 \%60% 的数据，n≤100n \leq 100n≤100，v≤2×103v \leq 2 \times 10^3v≤2×103.
枚举等差数列前 222 项，然后算出公差，往后枚举即可。
时间复杂度：O(n3)O(n^3)O(n3).
实际得分：60pts60pts60pts ~ 100pts100pts100pts.（取决于程序常数）
算法三对于另外 20%20 \%20% 的数据，所有电塔的高度构成一个等差数列。
显然，这时答案就相当于在 111 ~ nnn 中取等差数列。
为什么呢？这时，只要取等差数列 x,x+y,x+y⋯x+kyx, x+y , x+y \cdots x+kyx,x+y,x+y⋯x+ky，则在 原数列 中对应的数列为：
ax,ax+y⋯ax+kya_x , a_{x+y} \cdots a_{x+ky}ax,ax+y⋯ax+ky
必然为等差数列，并且每个数列对应一个这样的 等差数列。
那么，你用上面 60%60 \%60% 的暴力优化一下，枚举任意的两个点都可以形成等差数列，计算即可。
当然有一种特殊情况：即 ai=aj(i≠j)a_i = a_j (i \not = j)ai=aj(i=j) 时，任意的子序列都可以形成答案，答案为 2n−12^n-12n−1.
加上前面的 60%60 \%60% 的暴力：
时间复杂度：O(n3)O(n^3)O(n3).
实际得分：80pts80pts80pts ~ 100pts100pts100pts.（仍取决于程序常数）
算法四考虑 dp\text{dp}dp.
用 fi,jf_{i,j}fi,j 表示，以 iii 结尾的公差为 jjj 的等差数列个数。
当然我们不必枚举 jjj，我们枚举 k<ik<ik<i 的一个 kkk，并让 j=ai−akj = a_i - a_kj=ai−ak 进行转移。
所以（不考虑负下标问题）状态转移方程 为：
fi,ai−ak=fk,ai−ak+1f_{i,a_i - a_k} = f_{k,a_i - a_k} + 1fi,ai−ak=fk,ai−ak+1
显然，用前面一个 相同公差 的数列进行转移。
最后记得把长度为 111 ，222 的等差数列加上。
处理负下标，我们把所有下标（第二维）加上 NNN ，开大数组即可。
时间复杂度：O(n2)O(n^2)O(n2).
实际得分：100pts100pts100pts.
#pragma GCC optimize(2)
#include
using namespace std;
const int MOD=998244353;
const int N=1e3+1;
const int M=4e4+1;
inline int read(){char ch=getchar();int f=1;while(ch'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int n,a[N],ans=0;
int f[N][M];
int main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i=1;j--) {
t=a[i]-a[j]; //公差
ans=(ans+f[j][t+N])%MOD; //记录答案
f[i][t+N]=(f[i][t+N]+f[j][t+N]+1)%MOD; //转移
}
} printf("%d\n",ans);
return 0;
}
作者：bifanwen
