【题解】石子染色 [背包DP]

石子染色

题目描述

$\text{Bob}$ 将 $x$ 个石子分为 $n$ 堆（$1\le n,x\le 2000$），第 $i$ 堆有 $a_i$ 个。$\text{Bob}$
会从数列 { p n } : p i = i \{p_n\}:p_i=i {pn​}:pi​=i（$1\le i\le n$）中任意选择若干个数组成集合 $S$。对于任意的 $i$（$1\le i\le n$），若 $i\in S$，那么 $\text{Bob}$ 会将第 $i$
堆染为红色，反之染为蓝色。记红色的石子总个数为 $r$，蓝色的石子总个数为 $b$，映射 $f$ 满足
$f(S)=|r-b|$。 当 $S$ 取遍时，求 $\left[\sum f(S)\right]\mathrm{mod}998244353$ 的值。

格式

Input

第一行为一个数 $T$（$T\le 3$），表示数据组数。

对于每组数据，第一行为两个数 $x,n$；第二行有 $n$ 个数，表示 $a_1,a_2,\cdots ,a_n$。

Output

$\left[\sum f(S)\right]\mathrm{mod}998244353$ 的值。

分析

我们知道

$$f(S)=|r-b|,x=r+b$$

那么有

$$f(S)=|x-2b|$$

我们设 $S$ 的所有元素值和为 $i$ 的 $S$ 有 $s_i$ 个，那么就有

$$\sum f(S)=\sum |r-b|=\sum |x-2b|=\sum _{i=1}^x{s}_i|x-2i|$$

Code

#include 
#define MOD 998244353
using namespace std;
long long x, n, s[2005];
int       T;
int       main()
{
    // freopen("color.in", "r", stdio);
    // freopen("color.out", "w", stdio);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while (T--)
    {
        memset(s, 0, sizeof s);
        s[0] = 1;
        cin >> x >> n;
        for (int i(1), k; i <= n; ++i)
        {
            cin >> k;
            for (int j(x); j >= k; --j)
                s[j] = (s[j] + s[j - k]) % MOD;
        }
        long long ans = 0;
        for (int i(0); i <= x; ++i)
            ans = (ans + abs(x - 2 * i) % MOD * s[i] % MOD) % MOD;
        cout << ans << "\n";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

AD

$$\text{Lvshu OJ }\text{，大量高质量题目等着你，点击这里马上注册。}$$

$$\text{Lvshu OS}\text{，崭新的系统，点击这里，马上查看详情}$$