题解：CF1954D Colored Balls
Shunpower
·
·
题解
赛时脑子抽筋没调出来……
Statement
有 n 种颜色的小球，第 i 种颜色有 a_i 个。你可以把选择两个不同颜色的小球捆成一组，或者把一个小球单独成一组。对于一个颜色集，取出这些颜色的所有小球，这个颜色集的值就是这些小球的最少分组数。
你需要求出 n 种颜色的每一个子集的值。
## Solution
注意到将不同颜色的捆成一组这个操作非常像摩尔投票，所以我们直接考虑主元素，也就是球数量最多的颜色。下面我们认为主元素是出现次数**严格大于**集合大小一半的元素。
### 不存在主元素
设颜色集中颜色的小球总数是 $s$。特别地，如果 $s$ 是奇数，先扔掉小球数最多那种颜色的一个小球（必然不可能配完而扔掉它最优）把 $s$ 变成偶数。
考虑答案下界 $l=\frac{s}{2}$。
如果我们可以把这些小球分成长为 $l$ 的两段，并且每一段的同个位置上的小球颜色都不相同，那就取到了答案下界。考虑我们把每种颜色按照球数从多到少地往段里面塞，塞完第一段塞第二段。那么违背要求当且仅当某种颜色在第一段末尾没能塞完，塞到第二段开头结果重叠了，然而此时这个颜色的出现次数一定 $>\frac{s}{2}$，说明存在主元素，不符合预设条件。
所以我们证明了在不存在主元素的情况下，颜色集能取到它的答案下界，也说明了在 $s$ 为奇数的情况下丢掉小球数最多颜色的一个小球是最优的（丢了之后还是没有主元素，答案还可以取到下界）。综上，此类情况对总答案的贡献为 $\left\lfloor\frac{s+1}{2}\right\rfloor$。
### 存在主元素
此时我们可以把所有非主元素的颜色都去和主元素的颜色配完，然后主元素颜色里面可能还会剩一些小球，这些小球就只能一个一组。很容易可以发现这个分组方案是最优的。
考虑此时的组数。还是设颜色集中颜色的小球总数是 $s$，再设主元素颜色的小球数是 $m$，那么组数就是：
$$
s-m+m-(s-m)=m
$$
amazing 啊！也就是说这种情况对总答案的贡献就是主元素颜色的小球数。
那么整个做法就呼之欲出了。我们考虑把 $a$ 从小到大排序，显然随便编号颜色而不影响答案，所以我们让排序后的 $a$ 中第 $i$ 位表示颜色 $i$ 的小球存在 $a_i$ 个。
然后枚举颜色 $i$，钦定 $i$ 在颜色集中且是球数最多的颜色，也就是只考虑 $[1,i]$ 这些颜色加入颜色集且 $i$ 必须加入。则两种情况的贡献：
1. 对于所有总球数 $s\geq 2\times a_i$ 的情况，说明不存在主元素，于是每种情况贡献 $\left\lfloor\frac{s+1}{2}\right\rfloor$。
2. 对于所有总球数 $s< 2\times a_i$ 的情况，说明存在主元素，于是每种情况贡献 $a_i$。
显然这样统计是不重不漏的。下面考虑怎么数。
### 对于存在主元素
我们只需要数出来有多少种情况，直接用情况数乘 $a_i$ 就完事了。
设计一个背包。$g_{i,j}$ 表示前 $i$ 项总球数为 $j$ 的取颜色方案数，那么转移显然：
$$
g_{i,j+a_i}\gets g_{i-1,j}
$$
那么 $i$ 对总答案的贡献就是 $\sum\limits_{j=0}^{a_i-1} g_{i-1,j}\times a_i$，这里选择 $g_{i-1}$ 来统计答案的原因是钦定了必须选择颜色 $i$，但 $g_i$ 里面同时包括了选择与不选择两种可能，所以要选择用 $g_{i-1}$ 统计答案并改变枚举下标的范围。
### 对于不存在主元素
设计一个背包。$f_{i,j}$ 表示前 $i$ 项，选出的颜色集的总球数为 $j$ 个时所有的取颜色情况的 $\left\lfloor\frac{j+1}{2}\right\rfloor$ 的和。
容易通过分类讨论 $a_i,j$ 的奇偶性并使用 $g$ 辅助转移。
$$
f_{i,j+a_i}=\begin{cases}
f_{i-1,j}+g_{i-1,j}\times \left\lfloor\frac{a_i+[j \text{ is odd}]}{2}\right\rfloor,&a_i\text{ is odd}\\
f_{i-1,j}+g_{i-1,j}\times \left\lfloor\frac{a_i}{2}\right\rfloor,&a_i\text{ is even}\\
\end{cases}
$$
转移中的 $[]$ 是艾佛森括号。
那么 $i$ 对总答案的贡献就是 $\sum\limits_{j=2\times a_i}^{\infty} (f_{i,j}-f_{i-1,j})$。这里做减法的原因是钦定了必须选择颜色 $i$，从 $[1,i]$ 的所有情况里扣除 $[1,i-1]$ 的所有情况才能剩下一定选择了颜色 $i$ 的情况。
然后就做完了，想清楚了才好写。注意 $f$ 数组第二维要开到 $10^4$，因为下标要使用到 $2\times a_i$。
## Code
```cpp
const ll mod=998244353;
int n;
int a[N];
ll dp[2][N<<1];
ll cnt[2][N<<1];
ll tmp[N<<1];
ll tmp2[N<<1];
ll ans=0;
int main(){
#ifdef Griffin
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
ios::sync_with_stdio(false);
cin>>n;
fr1(i,1,n) cin>>a[i];
sort(a+1,a+n+1);
dp[0][0]=1;
int op=1;
fr1(i,1,n){
fr1(j,0,10000) tmp[j]=dp[op^1][j];
fr1(j,0,10000){
int x=j+a[i];
(tmp[x]+=dp[op^1][j])%=mod;
}
fr1(j,0,10000) dp[op][j]=tmp[j];
fr1(j,0,10000) tmp[j]=cnt[op^1][j]*(!(j&1)),tmp2[j]=cnt[op^1][j]*(j&1);
fr1(j,0,10000){
int x=j+a[i];
if(a[i]&1){
if(j&1) (tmp[x]+=cnt[op^1][j]+1ll*dp[op^1][j]*(a[i]/2)%mod)%=mod;
else (tmp2[x]+=cnt[op^1][j]+1ll*dp[op^1][j]*((a[i]+1)/2)%mod)%=mod;
}
else{
if(j&1) (tmp2[x]+=cnt[op^1][j]+1ll*dp[op^1][j]*(a[i]/2)%mod)%=mod;
else (tmp[x]+=cnt[op^1][j]+1ll*dp[op^1][j]*(a[i]/2)%mod)%=mod;
}
}
fr1(j,0,10000) cnt[op][j]=tmp[j]*(!(j&1)),cnt[op][j]+=tmp2[j]*(j&1);
fr1(j,a[i]*2,10000) (ans+=(cnt[op][j]-cnt[op^1][j])%mod)%=mod;
fr1(j,0,a[i]-1) (ans+=1ll*dp[op^1][j]*a[i]%mod)%=mod;
op^=1;
}
cout<<ans<<'\n';
ET;
}
```