自动搬运

查看原文

来自洛谷，原作者为

	chengni **

搬运于2025-08-24 22:05:25，当前版本为作者最后更新于2018-10-23 06:21:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我感觉我被题解限制了思路

其实这道题是 $O(n^2)$ 的

对于两个数字，他们组成的等差数列的公差一定是一样的

那么我们不必去枚举公差，直接枚举第 $i$ 个数前面那个数，得到公差进行转移即可

用 $f[i][j]$ 表示以 $i$ 结尾公差为 $j$ 的等差数列个数

转移如下

	int p=20000;
	for(int i=1;i<=n;i++){
        ans++;
        for(int j=i-1;j;j--){
            f[i][a[i]-a[j]+p]+=f[j][a[i]-a[j]+p]+1;
            f[i][a[i]-a[j]+p]%=mod;
            ans+=f[j][a[i]-a[j]+p]+1;
            ans%=mod;
        }
    }

以 $i$ 结尾且上一个数是 $j$ 的公差为 $k$ 的等差数列数量是以 $j$ 结尾公差为 $k$ 的等差数列数加一

转移的过程中直接计数，顺便把数字数为一的区间加上

注意第二维数组开二倍将负数右移即可

这样只需要 $n^2$ 的转移就可以了