CF1798F

xujindong_ · 2025-02-24 17:28:11 · 题解

这个题的核心结论是 Erdős-Ginzburg-Ziv 定理：对于任意 2n-1 个整数，总可以从中选出 n 个整数使它们的和为 n 的倍数。

引理一：对于任意的 n,m，若定理成立，则其也对 nm 成立。

对于 2nm-1 个数，先取出 n-1 个数，此时还剩 (2m-1)n 个数。重复 2m-1 次以下过程：每次加入 n 个数，在 2n-1 个数中取出 n 个数使其和是 n 的倍数。最后会得到 2m-1 组数，每组 n 个，且每组的和为 n 的倍数，取出 m 组使和为 m 的倍数即可。

引理二：定理对所有质数成立。

当众数出现大于等于 n 次，取出 n 个众数即可。

否则，可以将数划分为 n-1 对和一个单独的数，每一对中的数不相同。这个排序后第 i 个和第 n-i+1 个配对即可。先选上每对一个和单独的数，设和模 n 余 r，此时相当于有 n-1 个模 n 非 0 的数，分别为每对中选的数和未选数的差，要用这些数凑出任意一个模 n 余 r。

考虑构造出一颗树，编号 0\sim n-1，边权是这 n-1 个数，且 0 号节点到 i 号节点的距离模 n 为 i，最后节点 r 到根的路径即为所求。

考虑从根节点不断扩展，按顺序连边，每次连接树内一点和树外一点，则一定能构造出一种合法方案。假设当前边无法连接，设边权为 w，因为 0 在树中，所以 w 在树中。类似地，2w\bmod n,3w\bmod n,\cdots,kw\bmod n 在树中。因为 n 是质数，所以 kw\bmod n 遍历所有点，此时所有点都已加入树中。

对于此题，根据 EGZ 定理，当有至少 2s_i-1 个盒子时一定有解。将 s_i 从小到大处理，每次取 2s_i-1 个盒子构造 EGZ，则除了最大值外都可以满足。设 f_{i,j,k} 为前 i 个取了 j 个余数为 k，用一个背包 O(\frac{n^3}w) 求解。最大值用自己准备的盒子调整即可。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[205],s[205],id[205],pos,ans[205][205],q[205],cnt,temp[205];
bitset<205>f[205][205];
bool cmp(int a,int b){
  return s[a]<s[b];
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=1;i<=m;i++)cin>>s[i],id[i]=i;
  sort(id+1,id+m+1,cmp);
  for(int i=1;i<m;i++){
    int t=s[id[i]];
    while(cnt<2*t-1)q[++cnt]=a[++pos];
    for(int x=0;x<2*t;x++)for(int y=0;y<=t;y++)f[x][y].reset();
    f[0][0][0]=1;
    bitset<205>r;
    for(int x=0;x<t;x++)r[x]=1;
    for(int x=1;x<2*t;x++){
      for(int y=0;y<=t;y++)f[x][y]=f[x-1][y];
      for(int y=1;y<=t;y++)f[x][y]|=f[x-1][y-1]<<(q[x]%t)|f[x-1][y-1]>>(t-q[x]%t),f[x][y]&=r;
    }
    int now=0,num=0;
    for(int x=2*t-1,y=t,z=0;x>0;x--){
      if(f[x-1][y][z])temp[++now]=q[x];
      else ans[id[i]][++num]=q[x],y--,z=((z-q[x])%t+t)%t;
    }
    cnt=now,memcpy(q,temp,sizeof(q));
  }
  while(pos<n)q[++cnt]=a[++pos];
  int sum=0;
  for(int i=1;i<=cnt;i++)sum=(sum+q[i])%s[id[m]];
  cout<<s[id[m]]-sum<<'\n',memcpy(ans[id[m]],q,sizeof(ans[id[m]])),ans[id[m]][cnt+1]=s[id[m]]-sum;
  for(int i=1;i<=m;i++)for(int j=1;j<=s[i];j++)cout<<ans[i][j]<<(j==s[i]?'\n':' ');
  return 0;
}

对于 EGZ 定理，上面的定理已经天然地给出了一个构造方法。瓶颈在于构造树时快速找一个 k 使 kw\bmod n 在树中且 (k+1)w\bmod n 不在树中。考虑二分。先随便找一个 k 使 kw\bmod n 不在树中作为二分右边界，这可以随便找一个不在树中的点 q，k=qw^{-1}\bmod n。虽然没有单调性，但在二分过程中可以始终保持左端点在树中，右端点不在树中，最终必能找到合法点。O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
int n,m,prime[205],lpf[205],a[205],s[205],q[205],cnt,temp[205],pos;
bool vis[205],f[205];
pair<int,int>id[205];
vector<int>ans[205];
template<typename T>T qpow(T a,T b,T n,T ans=1){
  for(a%=n;b;b>>=1)b&1&&(ans=1ll*ans*a%n),a=1ll*a*a%n;
  return ans;
}
template<typename T>T inv(T a,T b){
  return qpow(a,b-2,b);
}
int prime_init(int n,int prime[],int lpf[],bool a[],int cnt=0){
  lpf[1]=1;
  for(int i=2;i<=n;i++)a[i]=1;
  for(int i=2;i<=n;i++){
    if(a[i])prime[++cnt]=i,lpf[i]=i;
    for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
      a[i*prime[j]]=0,lpf[i*prime[j]]=prime[j];
      if(i%prime[j]==0)break;
    }
  }
  return cnt;
}
void solve(int n,int a[],bool ans[]){
  int cnt[n],f[n],v[n],r=0;
  bool vis[n];
  pair<int,int>id[2*n];
  memset(cnt,0,sizeof(cnt)),memset(vis,0,sizeof(vis)),vis[0]=1;
  for(int i=1;i<2*n;i++)cnt[a[i]%n]++,ans[i]=0,id[i]=make_pair(a[i]%n,i);
  for(int i=0;i<n;i++){
    if(cnt[i]>=n){
      for(int j=1,num=0;num<n;j++)if(a[j]%n==i)ans[j]=1,num++;
      return;
    }
  }
  sort(id+1,id+2*n);
  for(int i=n;i<2*n;i++)r=(r+id[i].first)%n;
  for(int i=1,w,p=1;i<n;i++){
    w=(id[n+i-1].first-id[i].first+n)%n;
    while(vis[p])p++;
    int l=0,r=1ll*p*inv(w,n)%n;
    while(l+1<r){
      int mid=(l+r)>>1;
      if(vis[1ll*mid*w%n])l=mid;
      else r=mid;
    }
    f[1ll*r*w%n]=1ll*l*w%n,v[1ll*r*w%n]=i,vis[1ll*r*w%n]=1; 
  }
  memset(vis,0,sizeof(vis));
  while(r)vis[v[r]]=1,r=f[r];
  for(int i=1;i<n;i++){
    if(vis[i])ans[id[i].second]=1;
    else ans[id[n+i-1].second]=1;
  }
  ans[id[2*n-1].second]=1;
}
void egz(int n,int a[],bool ans[]){
  if(lpf[n]==n){
    solve(n,a,ans);
    return;
  }
  int x=lpf[n],y=n/x,q[2*x],id[2*x],temp1[2*x],temp2[2*x],b[2*y][x],sum[2*y];
  bool f[2*x],g[2*y];
  memset(sum,0,sizeof(sum));
  for(int i=1;i<2*n;i++)ans[i]=0;
  for(int i=1;i<x;i++)q[i]=a[i],id[i]=i;
  for(int i=1,pos=x-1,cnt=x-1;i<2*y;i++){
    while(cnt<2*x-1)q[++cnt]=a[++pos],id[cnt]=pos;
    solve(x,q,f);
    int now=0,num=0;
    for(int j=1;j<=cnt;j++){
      if(f[j])b[i][num++]=id[j],sum[i]+=q[j];
      else temp1[++now]=q[j],temp2[now]=id[j];
    }
    cnt=now;
    for(int j=1;j<=cnt;j++)q[j]=temp1[j],id[j]=temp2[j];
  }
  for(int i=1;i<2*y;i++)sum[i]/=x;
  egz(y,sum,g);
  for(int i=1;i<2*y;i++)if(g[i])for(int j=0;j<x;j++)ans[b[i][j]]=1;
}
int main(){
  cin>>n>>m,prime_init(n+1,prime,lpf,vis);
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=1;i<=m;i++)cin>>s[i],id[i]=make_pair(s[i],i);
  sort(id+1,id+m+1);
  for(int i=1;i<m;i++){
    int t=id[i].first;
    while(cnt<2*t-1)q[++cnt]=a[++pos];
    egz(t,q,f);
    int now=0;
    for(int j=1;j<=cnt;j++){
      if(f[j])ans[id[i].second].push_back(q[j]);
      else temp[++now]=q[j];
    }
    cnt=now;
    for(int j=1;j<=cnt;j++)q[j]=temp[j];
  }
  while(pos<n)q[++cnt]=a[++pos];
  int sum=0;
  for(int i=1;i<=cnt;i++)sum=(sum+q[i])%id[m].first,ans[id[m].second].push_back(q[i]);
  cout<<id[m].first-sum<<'\n',ans[id[m].second].push_back(id[m].first-sum);
  for(int i=1;i<=m;i++)for(int j=0;j<s[i];j++)cout<<ans[i][j]<<(j==s[i]-1?'\n':' ');
  return 0;
}