Submission #55606557

---

Source Code Expand

// {{{
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
#define debug(x...)
#define debug_arr(x...)
#ifdef LOCAL
#include "prettyprint.hpp"
#endif
// }}}

const int N = 111;
const int mod = 998244353;
int n;
LL a[N];
LL b[N];

LL dp[N][N];
LL ans[N];

int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif
    cin.tie(0)->sync_with_stdio(0);

    while (cin >> n)
    {
        for (int i = 1; i <= n; ++i) cin >> a[i];
        clr(ans, 0);
        ans[1] = n;

        // set<LL> ds, as;
        // ds.clear(), as.clear();
        // for (int i = 1; i <= n; i++)
        //{
        // as.insert(a[i]);
        // for (int j = i + 1; j <= n; j++) ds.insert(a[j] - a[i]);
        //}

        // vector<LL> dd = vector<LL>(all(ds));
        // vector<LL> aa = vector<LL>(all(as));

        set<pair<LL, LL>> st;
        for (int p = 1; p <= n; p++)
        {
            for (int q = p + 1; q <= n; q++)
            {
                LL a1 = a[p];
                LL d = a[q] - a[p];
                if (st.find({a1, d}) != st.end()) continue;
                st.insert({a1, d});

                for (int j = 1; j <= n; j++) b[j] = a1 + (j - 1) * d;

                for (int i = 0; i <= n; i++)
                    for (int j = 0; j <= n; j++) dp[i][j] = 0;

                for (int i = 0; i <= n; i++) dp[i][0] = 1;

                // n^2
                for (int i = 1; i <= n; i++)
                {
                    for (int j = 1; j <= n; j++)
                    {
                        dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
                        if (a[i] == b[j]) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
                    }
                }

                for (int ll = 2; ll <= n; ll++) ans[ll] = (ans[ll] + dp[n][ll]) % mod;
            }
        }

        for (int i = 1; i <= n; i++)
        {
            cout << ans[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

Submission Info

Judge Result