Submission #55544837

---

Source Code Expand

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
int MOD = 998244353;
const int N = 80;

int a[N];
ll memo[N+1][N+1];
ll n;
int barrier;
ll seed, diff;
// arithmetic sequences in (barrier, i] whose length is k
ll dp(int i, int k) {
    if (k == 2) {
        return 1;
    }
    if (i == barrier) {
        return 0;
    }
    if (memo[i][k] != -1) {
        return memo[i][k];
    }

    ll ans = dp(i-1, k); // skip
    if (a[i] == seed + (k-1)*diff) {
        ans = (ans + dp(i-1, k-1)) % MOD;
    }
    return memo[i][k] = ans;
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<ll> ans(n+1, 0);
    ans[1] = n;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            seed = a[i];
            diff = a[j] - a[i];
            barrier = j;
            memset(memo, -1, sizeof memo);
            for (int k = 2; k <= n; k++) {
                ans[k] = (ans[k] + dp(n-1, k)) % MOD;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
    return 0;
}

Submission Info

Judge Result