CF1798F 解题报告

Hoks · 2025-05-04 11:58:39 · 题解

前言

被结论题创飞了。

摘自杂题选做 Part 4. dp。

思路分析

做这题首先需要知道 Erdős-Ginzburg-Ziv 定理，不然完全没法下手。

Erdős-Ginzburg-Ziv 定理：n 是一个任意的正整数，则在 2n-1 个无限制整数中，必定存在 n 个整数，他们的和是 n 的倍数。

我们不难发现这个 2n-1 是一个下限。

对于 2n-2，我们可以考虑构造 n-1 个 0 和 n-1 个 1，此时凑不出 0 也凑不出 n，所以不是 n 的倍数。

然后我们来考虑怎么证明这个定理。

下面给出一种比较人类智慧的证明方法。

具体思路大概是证明素数情况成立，然后证明具有积性从而覆盖所有正整数。

我们先来考虑 n 为素数的情况。

此时我们不妨设这 2n-1 个数分别为 a_1,a_2,\dots,a_{2n-1}，且满足 0\le a_1\le a_2\le\dots\le a_{2n-1}<n，这是不失一般性的。

当 a_i=a_{i+n-1}(i\le n) 时，显然是成立的，因为至少有 n 个相同的数出现，加一块的和一定是 n 的倍数。

否则我们就有：\forall a_i\not=a_{i+n-1}(i\le n)。

考虑证明一个更强的命题 \forall w,\exist A\in\{a_1,a_2,\dots,a_{2n-1}\},|A|=n,\sum\limits_{x\in A}x\equiv w\pmod n。

也就是说我们可以找到 n 个大小为 n 的集合构成模 n 的完系。

证明而言我们考虑利用 \forall a_i\not=a_{i+n-1}(i\le n)，不妨定义 S_i=\{a_i,a_{i+n-1}\}(i<n)，特殊的我们有 S_n=\{a_{2n-1}\}。

再取 B_i=S_1+S_2+\dots+S_i(i<n) 组成的不可重集合，也就是模 n 意义下的和集。

我们会有 |B_1|=2（因为 a_1\not=a_n）。

那么其实我们有一个结论是 |B_i|\ge i+1。

证明考虑反证法，不妨假设 |B_x|\le i，且 x 为最小的满足这个条件的数。

那我们有 |B_{x-1}|>x-1,|B_{x-1}|\le|B_x|\le x。

把第一个式子变成 \le 接起来可以得到：x\le|B_{x-1}|\le|B_x|\le x。

那么就有 |B_{x-1}|=|B_x|=x。

我们考虑定义 C=B_{x-1}+\{a_x\},D=B_{x-1}+\{a_{x+n-1}\}。

那么我们有 x=|B_{x-1}|\le C,D\le |B_x|=x。

也就是可以得到 C=D\pmod n。

因为我们有 \forall a_i\not=a_{i+n-1}(i\le n)，且对一个模 n 环进行两次位移不同的平移后得到的环肯定是不同的。

所以我们可以得到当且仅当 C 为模 n 意义下的完系，才可能有 C=D\pmod n。

回忆下上文对于 x 的限制，我们有 x<n。

也就是 |C|=x<n，必然不可能是完系。

也就是上文的假设是错误的，可以得到 \forall i,|B_i|\ge i+1。

注意到 |B_{n-1}|\ge n，即为模 n 的完系。

那么我们定义 C=B_{n-1}+A_n，就有 C 亦为模 n 的完系。

同时根据和集的定义，我们知道 C 中的每一个元素都可以用 a_{b_1}+a_{b_2}+\dots+a_{b_n},1\le b_i\le 2n-1 表示出来。

也就是说我们可以选出 n 个 a 序列中的数来构成 C 中的任何一个数，即为构成一个模 n 的完系。

也就是原命题得证。

通过原命题我们也不难得到当 n 为素数时定理是成立的。
然后我们来证明这个命题是积性的，也就是如果对于 n 成立，对于 m 成立，那么对于 nm 也成立。

我们不妨设这 2nm-1 个数分别为 a_1,a_2,\dots,a_{2nm-1}。

不妨从中取出 2n-1 个数，那么我们知道对于这 2n-1 个数有一定可以取出 n 个数满足其和为 n 的倍数。

不失一般性而言，我们不妨设这 n 个数是 a_1,a_2,\dots,a_n，则我们有 n\mid\sum\limits_{i=1}^n a_i。

再取出 a_{n+1},a_{n+2},\dots,a_{3n-1} 这 2n-1 个数，同理我们不妨设 n\mid\sum\limits_{i=n+1}^{2n} a_i。

一直这样做下去我们就可以得到：
n\mid\sum\limits_{i=1+kn}^{(k+1)n} a_i(0\le k\le2m-2)
令 b_{k+1}=\sum\limits_{i=1+kn}^{(k+1)n} a_i(0\le k\le2m-2)，则有 \forall n\mid b_i(1\le i\le 2m-1)。

这里恰好有 2m-1 个数，所以我们可以从中取出 m 个数满足和为 m 的倍数，不妨设为 m\mid\sum\limits_{i=1}^m b_i。

显然的是由上面的条件我们还有 n\mid\sum\limits_{i=1}^m b_i。

但这样会有一些问题，这样推导出来的是积性不是完全积性。

当然也非常好解决，我们直接令 c_i=\frac{b_i}{n}(1\le i\le2m-1)，再套一步上面的得到 m\mid\sum\limits_{i=1}^m c_i，最后把分母 n 同意乘回去就可以得到 mn|\sum\limits_{i=1}^m b_i。

最后再把 b_i 用定义式展开就得到了：mn|\sum\limits_{i=1}^{nm} a_i。

这个显然是满足命题的，所以原命题得证。
最后一步就非常简单了，对于一个任意的正整数 n，我们将其质因数分解为 p_1^{a_1}p_2^{a_2}\dots p_m^{a_m}。

首先我们知道对于 p_1,p_2,\dots p_m 命题成立。接着通过 2. 中所证明的取 n=p_1,m=p_1^i 证明 p^{i+1} 成立从而得到 p_1^{a_1} 成立。

最后再把这些通过 2. 中证明的乘在一起就可以得到对 n 成立了，也就是我们证明了这个定理。

接着回归原题（证明好像是有点长了）。

首先我们根据定理知道，对于一个有着 s_i 个学生的班级，我们只需要 2s_i-1 个盒子就能保证能构造出一个倍数。

感性理解下这个部分，需要 2s_i-1 个盒子能保证构造，但是构造需要消耗 s_i 个盒子，不难发现先满足大的是不优秀的。

那我们按从小到大的顺序来尝试满足，则有 s_1\le s_2\le\dots\le s_k，且有 \sum\limits_{i=1}^k=n+1。

当我们考虑到 s_k 时，可以用新增的一个盒子直接来满足他。

接下来我们希望证明肯定可以满足剩下的 s_i。

极限情况即为 s_{k-1}，那么我们希望有 2s_{k-1}-1>n-\sum\limits_{i=1}^{k-2} s_i。

右边那个和式不好搞，我们直接由 \sum\limits_{i=1}^k s_i=n+1 把它化掉得到：

2s_{k-1}-1>n-(n+1-s_{k-1}-s_k)

s_{k-1}>s_k

这显然是和我们钦定的不降矛盾的。

也就是说对于任意的情况都有解，我们只需要从小到大的满足 s_1,s_2\dots,s_{k-1}，最后再多造一个盒子满足 s_k 即可。

接着是如何实现的问题。

我们考虑先枚举目前需要满足的是 s_i，然后枚举未用的盒子。

定义 f_{i,j,k} 表示前 i 个数取了 j 个能否得到模意义下的 k。

状态转移方程是平凡的就不再赘述，这样的复杂度是 O(n^3)。

可以考虑用过 bitset 在转移的时候前后分段断开平移拼接优化，这样就可以做到 O(\frac{n^3}{\omega})。

最后构造答案也是平凡的，根据我们的 dp 转移式子倒着跑回去就知道选了哪个数了。

注意记得添加最后一个数来补偿不足的部分。

代码

很好写，一遍过了。

#include<bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs (ls|1)
using namespace std;
const int N=200+10,M=2,V=80,mod=1e9+7,INF=1e10;
int n,m,a[N],mp[N];bool f[N][N][N];
pair<int,int>s[N];vector<int>ans[N];
namespace Fast_IO
{
    static char buf[1000000],*paa=buf,*pd=buf,out[10000000];int length=0;
    #define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
    inline int read()
    {
        int x(0),t(1);char fc(getchar());
        while(!isdigit(fc)){if(fc=='-') t=-1;fc=getchar();}
        while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
        return x*t;
    }
    inline void flush(){fwrite(out,1,length,stdout);length=0;}
    inline void put(char c){if(length==9999999) flush();out[length++]=c;}
    inline void put(string s){for(char c:s) put(c);}
    inline void print(int x)
    {
        if(x<0) put('-'),x=-x;
        if(x>9) print(x/10);
        put(x%10+'0');
    }
    inline bool chk(char c) { return !(c=='?'||c=='<'||c=='='||c>='a'&&c<='z'||c>='A'&&c<='Z'||c>='0'&&c<='9'); }
    inline bool ck(char c) { return c!='\n'&&c!='\r'&&c!=-1&&c!=' '; }
    inline void rd(char s[],int&n)
    {
        s[++n]=getchar();
        while(chk(s[n])) s[n]=getchar();
        while(ck(s[n])) s[++n]=getchar();
        n--;
    }
}
using namespace Fast_IO;
inline int del(int x,int y,int mod){return ((x-y)%mod+mod)%mod;}
inline void solve()
{
    n=read(),m=read();for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++) s[i]={read(),i};sort(s+1,s+1+m);
    for(int i=1,w;i<m;i++)
    {
        w=s[i].first;
        for(int j=1;j<=n;j++) for(int k=0;k<=j;k++)
            for(int l=0;l<w;l++) f[j][k][l]=0;
        f[0][0][0]=1;
        for(int j=1;j<=n;j++) for(int k=0;k<=min(w,j);k++)
            for(int l=0;l<w;l++)
            {
                if(f[j-1][k][l]) f[j][k][l]=1;
                if(!mp[j]&&k) f[j][k][l]|=f[j-1][k-1][del(l,a[j],w)];
            }
        for(int j=n,ss=0,tot=w;j>=1&&tot;j--)
        {
            if(mp[j]) continue;
            if(f[j-1][tot-1][del(ss,a[j],w)])
                ans[s[i].second].emplace_back(a[j]),mp[j]=1,ss=del(ss,a[j],w),tot--;
        }
    }int ss=0,id=s[m].second,w=s[m].first;
    for(int i=1;i<=n;i++) if(!mp[i]) ss+=a[i],ans[id].emplace_back(a[i]);
    ss%=w;print(w-ss);put('\n');ans[id].emplace_back(w-ss);
    for(int i=1;i<=m;i++,put('\n')) for(auto x:ans[i]) print(x),put(' ');
}
signed main()
{
    int T=1;
    // T=read();
    while(T--) solve();
    genshin:;flush();return 0;
}