题解归档 - cf2165B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2165B
• 本地来源：problems/cf2165B/idea.md
• 题目链接：https://codeforces.com/contest/2165/problem/B
• 原始标题：cf2165B Marble Council

思路

cf2165B Marble Council

Pattern

Counting supports with a small knapsack over frequencies.

Claim

Let f[x] be the original frequency of value x, and let S be the set of values that appear in the output multiset. A non-empty support S is feasible iff:

sum_{x in S} f[x] >= max_y f[y].

For a feasible support, each output count g[x] can be any integer from 1 to f[x], independently.

Necessary

Consider a value y with maximum original frequency. Every original copy of y must be placed into some output block. In a block whose selected mode is x in S, the number of y copies is at most the number of x copies in that block. Summing over all blocks gives f[y] <= sum_{x in S} f[x].

Sufficient

For a chosen support satisfying the inequality, first create g[x] blocks containing one copy of x for each output occurrence. The remaining support copies can be added to blocks of the same value. Then distribute non-support values among these blocks; the total support copies are enough to dominate every value frequency, so no block loses its selected mode after distribution.

Count

All non-empty output multisets ignoring feasibility: prod_x (f[x]+1)-1.

Subtract supports with total original frequency < mx, weighted by prod_{x in S} f[x]. Since mx <= n and sum n <= 5000, one DP over sums < mx is enough.

Brute / Check

Checked by samples and exact set-partition enumeration on small random multisets.

Edge

• one distinct value
• all values distinct
• several values tied for maximum frequency

代码

来源：problems/cf2165B/solution.cpp

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

const ll MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> cnt(n + 1, 0);
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            cnt[x]++;
        }

        vector<int> f;
        int mx = 0;
        for (int x = 1; x <= n; x++) {
            if (cnt[x]) {
                f.push_back(cnt[x]);
                mx = max(mx, cnt[x]);
            }
        }

        ll total = 1;
        for (int x : f) total = total * (x + 1) % MOD;
        total = (total - 1 + MOD) % MOD;

        vector<ll> dp(mx, 0);
        dp[0] = 1;
        for (int x : f) {
            for (int s = mx - 1; s >= x; s--) {
                dp[s] = (dp[s] + dp[s - x] * x) % MOD;
            }
        }

        ll bad = 0;
        for (int s = 1; s < mx; s++) bad = (bad + dp[s]) % MOD;
        ll ans = (total - bad + MOD) % MOD;
        cout << ans << '\n';
    }
    return 0;
}