题解：AT_cf17_final_f Distribute Numbers

Tx_Lcy · 2025-02-16 21:39:27 · 题解

脑电波题，但是我似乎没有对上脑电波，搞了一个略微复杂的做法。

思路

我们可以将“任意两张纸上有且仅有一个相同的数字”转化为：遍历每种数字，找出这种数字出现的纸的集合，随后将这个集合内的纸两两连边，最后要求每两张纸之间恰好连了一条边。

那么显然有必要条件：

\frac{n(n-1)}{2}=n\frac{k(k-1)}{2}

n-1=k(k-1)

我们取出 n \in [1000,2000] 的所有满足此条件的 (n,k)，发现还是有点多的，接下来考虑构造方案。

我们绘制一个 n \times n 的表格，横坐标表示纸，纵坐标表示值，在表格某个点 (x,y) 上染色就表示第 x 张纸上有值 y。

我们发现合法的条件就是任意两列染色的行集合交集为 1。

我们可以考虑先把前 k 列染成下图（n=13,k=4）这样，不难发现前 k 列此时是满足条件的。

对于后面的列我们可以考虑像下面这样一直染。

但是你发现染到第三组时就寄了。

自然地，我们可以考虑将第三组错开放，也就是这样：

这个所谓“错开放”的策略就是：

对于前 k 行我们每次放一段长度为 k-1 的，与前面错开。
对于第 k+1 \sim 2k-1 行，我们每次放一段边长为 k-1 的正方形的主对角线。
对于第 2k \sim n 行，我们每 k-1 行分一组，每 k-1 列分一组，都从 0 开始编号。设当前列在列中是第 i 组第 j 个，要在第 l 组行里染色，那么会染第 l 组行的第 (j+i \times l) \bmod (k-1) 个元素。

考虑一下这个策略何时会失效，也就是 j_1+i_1 \times l \equiv j_2+i_2 \times l \pmod {(k-1)}（i_1 \neq i_2）的解数不是 1 个。

j_1+i_1 \times l \equiv j_2+i_2 \times l \pmod {(k-1)}

j_1-j_2 \equiv i_2 \times l-i_1 \times l \pmod {(k-1)}

(i_2-i_1)l + (k-1)x=j_1-j_2

al+(k-1)x=b

显然有 l \in [0,k-1)，假设有两个不同解 a_1,a_2，那么：

a_1l+(k-1)x_1=a_2l+(k-1)x_2

(a_1-a_2)l=(k-1)(x_2-x_1)

当 k-1 是质数时，\gcd(l,k-1)=1，a_1-a_2 必须是 k-1 的倍数，但是由于 a_1 \neq a_2 且 |a_1|,|a_2| \in [0,k-1)，这是不可能的，因此此时最多有一个解，同时根据裴蜀定理，这个方程肯定有解，那么肯定恰好一个解。

所以我们取 k-1 是质数的一组 (n,k)，然后直接构造就做完了。

可以取 k=38。

代码

//A tree without skin will surely die.
//A man without face will be alive.
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define per(i,j,k) for (int i=j;i>=k;--i)
vector<int>vc[2005];int a[2005][2005];
inline bool prime(int x){
    rep(i,2,x-1) if (x%i==0) return 0;
    return 1;
}
inline void solve(){
    rep(n,1000,2000) rep(k,1,n)
        if (k*(k-1)==n-1 && prime(k-1)){
            cout<<n<<' '<<k<<'\n';
            int la=2;
            vector<int>g;
            rep(i,1,k){
                vc[i].push_back(1),g.push_back(la);
                rep(j,la,la+k-2) vc[i].push_back(j);
                la=la+k-1;
            }
            int cnt=0,D=0;
            rep(i,k+1,n){
                int gadd=cnt;
                for (auto it:g){
                    if (!vc[i].size()) vc[i].push_back(it+D);
                    else vc[i].push_back(it+gadd);
                    if (vc[i].size()>1) gadd+=D,gadd%=(k-1);
                }
                ++cnt;
                if (cnt==k-1) cnt=0,++D;
            }
            rep(i,1,n) for (auto j:vc[i])
                a[j][++a[j][0]]=i;
            rep(i,1,n){
                rep(j,1,a[i][0]) cout<<a[i][j]<<' ';
                cout<<'\n';
            }
            return;
        }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while (t--) solve();
    return 0;
}