P4933 大师

题目

P4933 大师

算法标签: 动态规划, 枚举

思路

注意到计算的是方案数量, 直接暴力枚举一定是无法通过的, 一般来说都是$dp$解决, 将整个答案的集合按照如下划分$f[i][d]$表示原序列中以$i$位置结尾的并且公差为$d$的所有方案的方案数, 状态转移就是枚举前面的所有位置的值, 观察是否能组成等差序列, 算法时间复杂度$O(n^2)$, 因为公差可能存在负数, 因此需要设置$offset=N$, 对所有公差$d$进行偏移

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 20010, M = 40020, MOD = 998244353;

int n, w[1010];
int f[1010][M];
bool vis[1010][M];
int ans;

void calc(int idx) {
   
    for (int i = idx - 1; i >= 1; --i) {
   
        int val = w[i] - w[idx] + N;
        if (!vis[i][val]) {
   
            f[i][val]++;
            vis[i][val] = true;
        }
        ans = (LL) (ans + f[i][val]) % MOD;
        f[idx][val] = (LL) (f[idx][val] + f[i][val]) % MOD;
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int i = 1; i <= n; ++i) calc(i);

    cout << (ans + n) % MOD << "\n";
    return 0;
}