企业官网建设流程全解析

形式化题意

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

Solution

图论建模，去掉自环后转化成在MMM个点的无向完全图上选出N∗N^*N∗个边不交的三元环。

设VVV为点集，E∗E^*E∗为所有出现在环中的边的集合。因为每条边至多出现在一个环中，所以存在映射f:E∗→Vf:E^*\to Vf:E∗→V，使得f({x,y})f(\{x,y\})f({x,y})为边{x,y}\{x,y\}{x,y}所在环的第三个点。同时，fff必须具有如下性质：

设f({x,y})=zf(\{x,y\})=zf({x,y})=z。则：
f({x,z})=yf({y,z})=x f(\{x,z\})=y\\ f(\{y,z\})=x\\f({x,z})=yf({y,z})=x

不难构造出f({x,y})=(−x−y) mod Mf(\{x,y\})=(-x-y)\bmod Mf({x,y})=(−x−y)modM。

然后暴力构造三元环，加上MMM个形如{x,x,x}\{x,x,x\}{x,x,x}的自环后恰好满足限制。

Code

#include"prison.h"#include<bits/stdc++.h>#definerep(i,a,b)for(inti(a);i<b;++i)#definerept(i,a,b)for(inti(a);i<=b;++i)usingnamespacestd;constintMAXM=4305,MAXN=3084000;structTri{intx,y,z;}a[MAXN];intM,N;intc[MAXM][MAXM];intsetup(int_M){M=_M;memset(c,-1,sizeof(c));rep(i,0,M){rep(j,i+1,M){if(c[i][j]==-1){intk=(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;}returnN;}vector<int>encode(intA){returnvector<int>({a[A].x,a[A].y,a[A].z});}intdecode(intX,intY){returnc[X][Y];}