洛谷-P14001 [eJOI 2025] Prison 题解

xiaoniu142857 · 2026-04-25 20:45:58 · 题解

形式化题意

构造至少 N^* 个值域为 [0,M) 的三元组，使得任意一对数至多在一个三元组中出现。

Solution

三元组可以分成如下三类：

1. 三个数均相同：形如 \{x,x,x\}。
2. 恰好两个数相同：形如 \{x,x,y\}。
3. 三个数均不同：形如 \{x,y,z\}。

我们希望 Bob 仅凭接收到的 2 个数就能推断出该三元组所属的类别。而第 2 类一定会与其它两类混淆。因此我们只构造第 1、3 类。

第 1 类是容易构造的，共有 M 个。

对于第 3 类，可以转化为在 M 个点的无向完全图上，选出足够多的边不交三元环。

为了保证边不交，对于每条边 \{x,y\}，必须存在映射 f(x,y)=z 来唯一确定第三个点，且满足对称性（即 f(x,z)=y 和 f(y,z)=x）。

最自然的构造是令三个顶点编号满足：

即 f(x,y)=(-x-y) \bmod M。

接下来排除退化情况。对于边 \{x,y\}，如果 f(x,y) 与它们重合，则该边无效。不妨假设 f(x,y)=x，则 y \equiv -2x \pmod M。

因此对于每个点 x，都有唯一无效边 \{x,-2x\} 与其对应，除非 x \equiv -2x \pmod M，即 3x \equiv 0 \pmod M。

若 3|M，则 3x \equiv 0 \pmod M 有 3 个解，否则有 1 个解。

综上，图中无效边数量为

从总边数中减去无效边，剩下的每 3 条边构成一个三元环。再加上第 1 类的 M 个三元组，我们总共构造了

个三元组，恰好满足限制。

Code

#include "prison.h"
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
using namespace std;
const int MAXM=4305,MAXN=3084000;
struct Tri{int x,y,z;}a[MAXN];
int N;
int c[MAXM][MAXM];
int setup(int M){
    memset(c,-1,sizeof(c));
    rep(i,0,M){
        rep(j,i+1,M){
            if(c[i][j]==-1){
                int k=(M*2-i-j)%M;
                if(k==i||k==j) continue;
                c[i][j]=c[i][k]=c[j][k]=c[j][i]=c[k][i]=c[k][j]=N;
                a[N]={i,j,k};
                ++N;
            }
        }
    }
    rep(i,0,M){
        c[i][i]=N;
        a[N]={i,i,i};
        ++N;
    }
    return N;
}
vector<int> encode(int A){
    return vector<int>({a[A].x,a[A].y,a[A].z});
}
int decode(int X,int Y){
    return c[X][Y];
}