洛谷 P4933 大师
只是提供思路：
dp[i][j]: 以 i 结尾公差为 j 的等差数列个数
转移：
以 i 结尾且上一个数是 j 的公差为 k 的等差数列数量是以 j 结尾公差为 k 的等差数列数加一
ans计算的是前一个等差序列dp[j][k]对当前dp[i][k]的贡献
关于为什么ans不用dp[i][d]更新：
-
f[i][d]是逐步更新的。在处理i的过程中，每遍历一个j，f[i][d]会累加来自不同j的贡献。 -
如果使用
ans += f[i][d] + 1，会导致重复统计：-
假设
i之前有两个不同的j1和j2，且它们与i的公差相同（d1 = d2）。 -
当处理
j1时，f[i][d1]会增加f[j1][d1] + 1，此时ans会累加一次。 -
当处理
j2时，f[i][d1]会再次增加f[j2][d1] + 1，此时若再累加f[i][d1]，会重复计算之前j1的贡献。
-
const int N = 1e3 + 10;
LL n;
LL a[N],dp[N][20010];
LL mo(LL x)
{
return (x % mod + mod) % mod;
}
void solve()
{
cin >> n;
for (int i = 1;i <= n;i ++) cin >> a[i];
LL ans = 0;
LL p = 20010;
for (int i = 1;i <= n;i ++)
{
ans = mo(ans + 1);//长度为1的等差数列
for (int j = 1;j < i;j ++)
{
LL d = a[i] - a[j] + p;
dp[i][d] = mo(dp[i][d] + dp[j][d] + 1);
ans = mo(ans + dp[j][d] + 1);//对于ap[i][d]形成了一个新的等差序列，相当于对ans贡献了一个dp[j][d]+1
}
}
cout << mo(ans) << endl;
}