题解 P4933 【大师】

chengni · 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 的转移就可以了