[刷题笔记] Luogu P4933 大师

Problem

Description

给定一个长度为 \(n\) 的数组 \(h\)，你可以从中选取若干数字，使得你选择的数组组成一个等差数列。特别地，单一的数字和只有两个数字也算作等差数列。求你可选择的方案数。答案对 \(998244353\) 取模。

Analysis

考虑 \(f_{i,j}\) 表示前 \(i\) 个数，公差为 \(j\) 时的方案数。

特别地，公差允许是负数，直接作为数组下标会溢出，所以我们可以整体偏移，也就是使 \(j\) 加上一个很大的数字。

公差 \(j\) 可以不用枚举，只需要枚举 \(i\) ，对于每一个 \(i\)，\(a_i-a_k(\forall k < i)\) 即为公差。需要注意必须是 \(a_i-a_k\) ，而不能是 \(a_k-a_i\)。

考虑转移，\(f_{i,a_i-a_k}+=f_{k,a_i-a_k}+1\)。直接拼接即可。不会少算，因为是 \(+=\)，每次只在 \(a_k\) 的后面拼接。

那么我们的 \(answer\) 该如何计算呢？

我们显然不希望重复计算方案数。

如果每次加上更新完后的 \(f_{i,a_i-a_k}\) 显然会重复加很多，我们实际上每次只需要使 ans 加上 \(f_{k,a_i-a_k}+1\) 即可。显然 \(f_{i,a_i-a_k}\) 也是在这个基础上累加。这样就确保了每种情况只计算一遍。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int p = 10000;
const int N = 10100;
const int mod = 998244353;
int n;
int a[N];
int ans = 0;
int f[N][N*4];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {   
        cin>>a[i];
    }
    for(int i=1;i<=n;i++) 
    {
        for(int j=1;j<i;j++) //枚举公差
        {
            f[i][a[i]-a[j]+p] += f[j][a[i]-a[j]+p] + 1; //更新前 $i$ 位公差为 $a_i-a_j$ 的数量
            f[i][a[i]-a[j]+p] %= mod; 
            ans += f[j][a[i]-a[j]+p]+1; // ans +的一定不能是 $f_{i,a_i-a_j+p}$。若如此操作则会重复
            ans %= mod;
        }
    }
    cout<<ans+n<<endl;
    return 0;
}