自动搬运

查看原文

来自洛谷，原作者为

	ty_mxzhn 打破天生的劣等感 || 写作悔恨的未来

搬运于2025-08-24 22:49:02，当前版本为作者最后更新于2023-08-10 14:42:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于每两个平均数相同的划分方案里的子集 $S,T$，可以合并成一个子集。

那我们只需要把数分成两个子集即可。根据此，可知题目所知的相等的平均数即为整个数列的平均数。

显然可以将每个数减去这个平均数。此时问题转化为，$\texttt{Yes}$ 即找到转化后的一个非全选，非全不选的和为 $0$ 的子序列。

这里显然列出 dp：$f_{i,j}$ 为前 $i$ 个数中和为 $j$ 的方案。$f_{i,j}=f_{i-1,j}+f_{i-1,j-a_i}$。答案即为 $[f_{n,0}\geq 3]$

发现肯定过不了，但我们有同余科技，如果把和为 $j$ 改为和 $\bmod p=j$，就很轻松了，于是多判几次即可。

#include <cstdio>
#include <cstring>
using namespace std;

int t,n,a[1007];
short f1[7][1007][2007],g1[7][1007][2007];
int s,p[]={0,1799,1857,1927,1924,1981,1999};//判断的模数
signed main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);s=0;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]),s=s+a[i];
		if(s%n!=0){
			printf("No\n");//没有平均数
			continue;
		}
		s=s/n;
		memset(f1,0,sizeof f1);
		memset(g1,0,sizeof g1);
		for(int i=1;i<=n;i++) a[i]=a[i]-s;//问题转化
		for(int k=1;k<=6;k++){
			g1[k][0][0]=f1[k][0][0]=1;
			for(int i=1;i<=n;i++){
				for(int j=0;j<p[k];j++){
					f1[k][i][j]=g1[k][i-1][(j-a[i]+p[k]+p[k]+p[k])%p[k]];
					g1[k][i][j]=g1[k][i-1][j]+f1[k][i][j];
					if(g1[k][i][j]>10000) g1[k][i][j]=10000;//这里显然可以剪去情况
				}
			}
		}
		int ans=1;
		for(int k=1;k<=6;k++){
			ans=ans&&(g1[k][n][0]>=3);//所有模数都要过
		}
		if(ans) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}