序列s中的数就是要选的堆的编号，假设要选的有i个石子，这i个染为红色，剩下j个染为蓝色，i+j=x，i=x-j，那么对答案的贡献是|x-2j|。那么只要我们选的有i个石子，贡献就是这么多，所以我们可以求出选取数量为i的方案数有si个，那么答案就是∑ | − 2| (1=<i<=x).
用背包DP处理出si，最后统计答案即可。
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define Mod 998244353
4 int x,n,f[2005];
5
6 int main(){
7 int T;cin>>T;
8 while(T--){
9 memset(f,0,sizeof(f));f[0]=1;
10 cin>>x>>n;
11 for(int i=1;i<=n;i++){
12 int k;cin>>k;
13 for(int j=x;j>=k;j--)
14 f[j]=(f[j]+f[j-k])%Mod;
15 }
16 long long ans=0;
17 for(int i=0;i<=x;i++)
18 ans=(ans+abs((long long)(x-2*i)*f[i]%Mod))%Mod;
19 cout<<ans<<endl;
20 }
21 return 0;
22 }
![P1880 [NOI1995] 石子合并 题解](https://www.kunjuke.com/file/css/thumb/1.jpg/280-180.jpg)
![[NOI.AC省选模拟赛3.23] 染色 [点分治+BFS序]](https://www.kunjuke.com/file/css/thumb/6.jpg/280-180.jpg)
