Counting Sort?

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MOD = 998244353;
const int MAXN = 50;

struct ArrayHash {
    size_t operator()(const array<uint8_t, MAXN + 1>& a) const noexcept {
        size_t h = 0;
        for (int i = 1; i <= MAXN; ++i) {
            h = h * 1315423911u + a[i];
        }
        return h;
    }
};

struct PartInfo {
    int sum;
    int parts;
    bool distinct;
    bool isSingle;
};

vector<PartInfo> infos;
vector<array<uint8_t, MAXN + 1>> mults;
unordered_map<array<uint8_t, MAXN + 1>, int, ArrayHash> mp;
int emptyId, id1;

int Cbin[MAXN + 1][MAXN + 1];
vector<int> partSum;
vector<int> Hval;
vector<int> trans;
vector<int> off;
vector<int> idsBySum[MAXN + 1];

void genPartitions(int rem, int maxPart, int sum, vector<int>& cur, array<uint8_t, MAXN + 1>& mult) {
    auto it = mp.find(mult);
    if (it == mp.end()) {
        int id = (int)infos.size();
        mp[mult] = id;
        PartInfo p;
        p.sum = sum;
        p.parts = (int)cur.size();
        p.distinct = true;
        for (int k = 1; k <= MAXN; ++k) {
            if (mult[k] > 1) { p.distinct = false; break; }
        }
        p.isSingle = (cur.size() == 1);
        infos.push_back(p);
        mults.push_back(mult);
    }
    for (int part = min(maxPart, rem); part >= 1; --part) {
        mult[part]++;
        cur.push_back(part);
        genPartitions(rem - part, part, sum + part, cur, mult);
        cur.pop_back();
        mult[part]--;
    }
}

void precompute() {
    for (int n = 0; n <= MAXN; ++n) {
        Cbin[n][0] = Cbin[n][n] = 1;
        for (int k = 1; k < n; ++k) {
            Cbin[n][k] = Cbin[n-1][k-1] + Cbin[n-1][k];
            if (Cbin[n][k] >= MOD) Cbin[n][k] -= MOD;
        }
    }

    vector<int> cur;
    array<uint8_t, MAXN + 1> mult{};
    genPartitions(MAXN, MAXN, 0, cur, mult);
    int P = (int)infos.size();
    partSum.resize(P);
    for (int i = 0; i < P; ++i) partSum[i] = infos[i].sum;

    for (int i = 0; i < P; ++i) {
        idsBySum[partSum[i]].push_back(i);
    }

    off.resize(P + 1);
    off[0] = 0;
    for (int i = 0; i < P; ++i) {
        off[i+1] = off[i] + (MAXN - infos[i].sum);
    }
    int T = off[P];
    trans.resize(T);
    for (int id = 0; id < P; ++id) {
        auto m = mults[id];
        int cnt = MAXN - infos[id].sum;
        for (int c = 1; c <= cnt; ++c) {
            m[c]++;
            trans[off[id] + (c - 1)] = mp[m];
            m[c]--;
        }
    }

    Hval.resize(P);
    vector<vector<int>> bySum(MAXN + 1);
    for (int i = 0; i < P; ++i) bySum[infos[i].sum].push_back(i);
    for (int s = 0; s <= MAXN; ++s) {
        for (int id : bySum[s]) {
            if (s == 0) {
                Hval[id] = 1;
            } else if (s == 1 && infos[id].isSingle) {
                Hval[id] = 2;
            } else if (infos[id].distinct) {
                Hval[id] = infos[id].isSingle ? 3 : 5;
            } else {
                array<uint8_t, MAXN + 1> mf{};
                for (int k = 1; k <= MAXN; ++k) {
                    uint8_t m = mults[id][k];
                    if (m > 0) mf[m]++;
                }
                int fid = mp[mf];
                Hval[id] = Hval[fid] + 1;
            }
        }
    }

    array<uint8_t, MAXN + 1> zero{};
    emptyId = mp[zero];
    array<uint8_t, MAXN + 1> m1{};
    m1[1] = 1;
    id1 = mp[m1];

    vector<PartInfo>().swap(infos);
    vector<array<uint8_t, MAXN + 1>>().swap(mults);
    unordered_map<array<uint8_t, MAXN + 1>, int, ArrayHash>().swap(mp);
}

void solveOne(int n, int k, const vector<int>& r) {
    vector<int> s(n + 2, 0);
    for (int i = 1; i <= n; ++i) {
        int ri = r[i-1];
        for (int v = 1; v <= ri; ++v) ++s[v];
    }
    int maxV = 0;
    for (int v = 1; v <= n; ++v) if (s[v] > 0) maxV = v;

    int P = (int)partSum.size();
    vector<int> cur(P), nxt(P);
    cur[emptyId] = 1;

    for (int v = maxV; v >= 1; --v) {
        fill(nxt.begin(), nxt.end(), 0);
        int sv = s[v];
        for (int sum = 0; sum <= sv; ++sum) {
            for (int id : idsBySum[sum]) {
                int val = cur[id];
                if (!val) continue;
                int R = sv - sum;
                int &ref0 = nxt[id];
                ref0 += val;
                if (ref0 >= MOD) ref0 -= MOD;
                int base = off[id];
                for (int c = 1; c <= R; ++c) {
                    int nid = trans[base + (c - 1)];
                    long long add = 1LL * val * Cbin[R][c] % MOD;
                    int &ref = nxt[nid];
                    ref += add;
                    if (ref >= MOD) ref -= MOD;
                }
            }
        }
        cur.swap(nxt);
    }

    vector<int> ans(k + 1, 0);
    ans[1] = (1 + (r[0] > 0)) % MOD;
    if (k >= 2) {
        ans[2] = (s[1] - (r[0] > 0)) % MOD;
        if (ans[2] < 0) ans[2] += MOD;
    }
    if (k >= 3) {
        long long v3 = (long long)cur[id1] - s[1];
        v3 %= MOD;
        if (v3 < 0) v3 += MOD;
        ans[3] = (int)v3;
    }
    for (int id = 0; id < P; ++id) {
        int h = Hval[id];
        if (h >= 3) {
            int p = h + 1;
            if (p <= k) {
                ans[p] += cur[id];
                if (ans[p] >= MOD) ans[p] -= MOD;
            }
        }
    }

    for (int p = 1; p <= k; ++p) {
        if (p > 1) cout << ' ';
        cout << ans[p];
    }
    cout << '\n';
}

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();
    precompute();
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<int> r(n);
        for (int i = 0; i < n; ++i) cin >> r[i];
        solveOne(n, k, r);
    }
    return 0;
}