2222HUnreviewedunratedKimi K2.6 (thinking)

Counting Sort?

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

brute force combinatorics dp

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Play with tiny $n$ and write out the orbits. How many fixed points does $f$ have? Does any array ever enter a cycle longer than $1$ ?

Prove that every non-zero array eventually reaches $e_1 = [1,0,\dots,0]$ . Consequently, for $a \notin \{0, e_1\}$ we have $g(a) = 1 + g(f(a))$ . So $g(a)$ is just "distance to $e_1$ plus one".

For a count vector $c$ , $g(c)$ depends only on the multiset of its positive entries—call that integer partition $\lambda$ . Define $H(\lambda)$ recursively via the "frequency-of-frequencies" map $F$ (the multiplicities of the parts). You'll find $H$ stays very small; for $n \le 50$ it never exceeds $9$ or $10$ .

Let $s_v = |\{i : r_i \ge v\}|$ . Because the sets $\{i : r_i \ge v\}$ are nested, the number of arrays with a fixed count vector $c$ is $\prod_v \binom{s_v - \sum_{u>v} c_u}{c_v}$ . We need to sum this over all $c$ whose positive entries form a given partition $\lambda$ .

Process values $v=n \dots 1$ . Maintain a DP over partitions $\lambda$ of the counts of already-processed values. From state $\lambda$ with $\operatorname{sum}(\lambda)$ there are $R = s_v - \operatorname{sum}(\lambda)$ free slots; choosing $c$ of them inserts a part $c$ into $\lambda$ and multiplies by $\binom{R}{c}$ . Precompute the partition graph and all $H(\lambda)$ ; then aggregate $M_\lambda$ into $\mathrm{ans}[H(\lambda)+1]$ .

Observation 1: The functional graph is a rooted tree

Define $f(b)=c$ where $c_i$ counts occurrences of $i$ in $b$ . Two obvious fixed points are $0$ and $e_1=[1,0,\dots,0]$ . A short counting argument on the equation $c_i = \#\{j : c_j=i\}$ shows these are the only fixed points. Moreover, if we look at the multiset of positive entries of $b$ (an integer partition), one step of $f$ replaces it by the partition of the multiplicities of its parts. The sum of parts strictly decreases under this map unless the partition is $(1)$ , and $(1)$ maps to itself. Hence every non-zero array eventually reaches $e_1$ , and there are no other cycles.

Consequences:

$g(0)=g(e_1)=1$ .
For every other array $a$ , $g(a)=1+g(f(a))$ .

So $g(a)$ is exactly the distance from $a$ to the root $e_1$ in the in-tree, plus one.

Observation 2: From arrays to partitions

$f(a)$ is a count vector $c\in\mathbb Z_{\ge0}^n$ . For a count vector $c\neq0,e_1$ , $g(c)=1+g(f(c))$ . Crucially, $f(c)$ depends only on the multiset of positive entries of $c$ , i.e. on an integer partition $\lambda$ . Let $H(\lambda)$ denote this common value. One checks:

$H((1))=2$ (this corresponds to $e_j$ , $j>1$ ).
$H((j))=3$ for $j>1$ .
If $\lambda$ has distinct parts and at least two parts, $H(\lambda)=5$ .
If $\lambda=(s^j)$ with $j>1$ (all parts equal, at least two of them), $H(\lambda)=4$ .
Otherwise $H(\lambda)=1+H(F(\lambda))$ , where $F(\lambda)$ is the partition of the multiplicities of part sizes in $\lambda$ .

Since $n\le50$ , $H(\lambda)$ never exceeds about $10$ .

Observation 3: Counting arrays with a given frequency partition

Let $s_v=|\{i:r_i\ge v\}|$ . Because the feasible sets $T_v=\{i:r_i\ge v\}$ are nested, the number of arrays $a$ with a prescribed count vector $c$ is $N(c)=\prod_{v=1}^n\binom{s_v-\sum_{u>v}c_u}{c_v}.$ For a partition $\lambda$ define $M_\lambda=\sum_{c\;:\;P(c)=\lambda} N(c),$ where $P(c)$ is the partition of the positive entries of $c$ . Then for $p\ge4$ $\text{ans}[p]=\sum_{\lambda:\,H(\lambda)=p-1} M_\lambda,$ while the first three values are obtained directly:

$\text{ans}[1]=1+[r_1\ge1]$ (arrays $0$ and $e_1$ ).
$\text{ans}[2]=s_1-[r_1\ge1]$ (arrays with exactly one $1$ , not $e_1$ ).
$\text{ans}[3]=\bigl(\sum_{j\ge2}s_j\bigr)=M_{(1)}-s_1$ .

Observation 4: DP over values

Process $v=n,n-1,\dots,1$ . After processing values $>v$ , the DP state is a partition $\lambda$ representing the positive counts among those values. Let $dp_v[\lambda]$ be the sum of the binomial products for the already processed values.

Transition: from state $\lambda$ with total $\operatorname{sum}(\lambda)$ we have $R=s_v-\operatorname{sum}(\lambda)$ free positions that can take value $v$ . Choose $c\in[0,R]$ of them. This contributes $\binom{R}{c}$ and, if $c>0$ , inserts a part $c$ into $\lambda$ .

The number of integer partitions of numbers $\le50$ is about $1.3\cdot10^6$ , and the total number of transitions over all $v$ is bounded by $n\sum_{\lambda}(n-\operatorname{sum}(\lambda))\approx 3\cdot10^8,$ easily fast enough.

Precomputation:

Generate all partitions of $0,\dots,50$ .
Precompute the transition "add a part $c$ " for every partition.
Precompute $H(\lambda)$ in order of increasing sum.
Run the value-DP for each test case and accumulate the answers.

Complexity: $O\big(n\sum_{\lambda}(n-\operatorname{sum}(\lambda))\big)$ per test case, which is $\le 4\cdot10^8$ elementary operations for $n=50$ . Memory is about $80$ MB.

#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;
}

#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;
}

View on Codeforces Back to the list