CF Educational Codeforces Round 164 Div.2 D. Colored Balls 题解

Colored Balls

题目描述

There are balls of $n$ different colors; the number of balls of the $i$-th color is $a_i$.

The balls can be combined into groups. Each group should contain at most $2$ balls, and no more than $1$ ball of each color.

Consider all $2^n$ sets of colors. For a set of colors, let’s denote its value as the minimum number of groups the balls of those colors can be distributed into. For example, if there are three colors with $3$, $1$ and $7$ balls respectively, they can be combined into $7$ groups (and not less than $7$), so the value of that set of colors is $7$.

Your task is to calculate the sum of values over all $2^n$ possible sets of colors. Since the answer may be too large, print it modulo $998244353$.

输入格式

The first line contains a single integer $n$ ($1\le n\le 5000$) — the number of colors.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 5000$) — the number of balls of the $i$-th color.

Additional constraint on input: the total number of balls doesn’t exceed $5000$.

输出格式

Print a single integer — the sum of values of all $2^n$ sets of colors, taken modulo $998244353$.

样例 #1

样例输入 #1

3
1 1 2

样例输出 #1

11

样例 #2

样例输入 #2

1
5

样例输出 #2

5

样例 #3

样例输入 #3

4
1 3 3 7

样例输出 #3

76

提示

Consider the first example. There are $8$ sets of colors:

• for the empty set, its value is $0$;
• for the set { 1 } \{1\} {1}, its value is $1$;
• for the set { 2 } \{2\} {2}, its value is $1$;
• for the set { 3 } \{3\} {3}, its value is $2$;
• for the set { 1 , 2 } \{1,2\} {1,2}, its value is $1$;
• for the set { 1 , 3 } \{1,3\} {1,3}, its value is $2$;
• for the set { 2 , 3 } \{2,3\} {2,3}, its value is $2$;
• for the set { 1 , 2 , 3 } \{1,2,3\} {1,2,3}, its value is $2$.

So, the sum of values over all $2^n$ sets of colors is $11$.

原题

洛谷——传送门

代码

#include <bits/stdc++.h>
using namespace std;
#define max_Heap(x) priority_queue<x, vector<x>, less<x>>
#define min_Heap(x) priority_queue<x, vector<x>, greater<x>>
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;

const ll mod = 998244353;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //根据题面提示：球的总数不超过5000
    //可知通过dp统计总和为i的集合个数，进行背包dp的背包容量不超过5000
    int n;
    cin >> n;
    vector<ll> v(n);
    //统计球总数
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        sum += v[i];
    }
    //背包dp数组
    vector<ll> dp(sum + 1, 0);
    //初始化总和为0的集合个数为1，即空集
    dp[0] = 1;
    //dp，统计总和为j的子集个数
    for (int i = 0; i < n; i++)
    {
        for (int j = sum; j >= v[i]; j--)
        {
            dp[j] += dp[j - v[i]];
            dp[j] %= mod;
        }
    }
    //存储答案：颜色组的个数
    ll ans = 0;
    //由于每个集合的答案有两种情况：
    //1.当集合中最大值小于等于集合总和一半时，答案为集合总和sum/2，若有余数则加1
    //2.当集合中最大值大于集合总和一半，答案为最大值
    //所以先假定均为情况一，统计所有答案，然后再处理其中情况二
    for (ll i = 0; i <= sum; i++)
    {
        ans += (i + 1) / 2 * dp[i];
        ans %= mod;
    }
    //处理情况二：
    //枚举第i+1种颜色球的个数
    for (int i = 0; i < n; i++)
    {
        //枚举所有总和小于v[i]的集合的个数，那么该集合再加上v[i]元素的新集合的统计就是情况二
        //而新集合的答案统计先前假定了情况一，所以需要减去情况一的值即（v[i]+j+1）/2 ，即集合总和除以二加上余数
        for (int j = 0; j < v[i]; j++)//当遍历所有小于v[i]的集合总和时，就已经确保了除了最大值以外的集合总和小于最大值
        {
            //同时答案需统计情况二，即最大值v[i]
            ans += (v[i] - (v[i] + j + 1) / 2) * dp[j];
            ans %= mod;
        }
    }
    cout << ans;

    return 0;
}