题解 P5271 【OwenOwl 不学车也不删库】
shadowice1984
2019-03-23 21:45:44
神仙构造题……
膜神O
__________________
## 本题题解
题意简单明了此处不在赘述
那么首先我们发现题目中要求我们构造的方案是$P^k$,这个限制条件绝对是在告诉我们"要分治"
那么我们不妨考虑通过分治法来构造我们的方案
换句话讲,我们希望构造出大小为$P^k$的方案,可以采取这样的一个算法流程
如果$k=1$那么可以直接输出$0\dots P-1$
否则我们递归下去构造出一个$P^{k-1}$的解,然后把这个解当中的点的编号分别加上$0,P^{k-1},2P^{k-1} \dots (P-1)P^{k-1}$各输出一下
此时我们发现如果两个点的编号除P下取整一样的话,那么这条边在之前的分治当中已经处理完毕了,此时我们可以认为为所有点被分成了$P$块,每块的长度都是$P^{k-1}$,如果两个点所在的块不同则没有边
**为了方便起见我们把点重新标号,膜$P^{k-1}$同余的点标号相同**,这样会方便我们构造之后的解,输出的时候只需要把点的标号加上所在块的编号×$P^{k-1}$即可还原真实的解
此时我们希望选择一些团覆盖这张图的所有边,这样我们就做完这道题啦~
那咋做呢?
首先先来思考一个很trivial的问题,我们到底要输出多少个团呢?
一共有$(P^{k-1})^2{P \choose 2}$条边,每个团可以覆盖${P \choose 2}$条边,所以我们要输出$(P^{k-1})^2$个团
那我们不妨对着这个平方开始编
不如重新整理一下我们的限制条件,在这一*-层分治我们要做的事情是,确定$P^{k-1}$个长度为$P$的数组,数组当中的每个数字在$[0,P^{k-1}]$之间,并且满足这个限制条件
**任意两个数组至多有1位相同**
注意到我们要构造平方个数组,这样实在是好烦啊,我们想一想能不能把我们的工作量减少一些,现在假装我们构造了$P^{k-1}$个符合上述条件的数组,我们将这些数组的每一位加上$0,1,2, \dots P^{k-1}-1$之后对$P^{k-1}$取膜,这样我们将**有可能**从$P^{k-1}$个数组拓展出一个有$(P^{k-1})^2$个数组
~~喔,你问我怎么编出来的?各种常见的构造方式挨个试一试,碰巧这种对着方案数编构造的方法奏效了而已~~
采取上述方式构造的话,初始的解需要满足以下的条件
**任意两个数组对应位置做差,不能存在相等的数字**
那这样的$P^{k-1}$个数组怎么构造呢?
稍微编了一会之后我们发现让第$i$个数组的第$j$位为$i×j \mod P^{k-1}$
就行了,这样显然任意两个数组做差之后都不存在相等的数字啊
~~喔,你问我这是怎么编出来的?当然还是各种数组胡乱试一试然后这个碰巧奏效啦~~
那这样我们就有了作为"种子"的初始$P^{k-1}$个解,就可以用它倒过来生成 那$(P^{k-1})^2$个数组啦,于是我们的分治法成功奏效这题就做完了……
听说这题卡输出于是写了个快速输出……速度惊人
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=2010;typedef long long ll;
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a)if(p&1)r=r*a;return r;}
char mde[N][6];int hd[N];
inline void pre()//这里写了个快速输出
{
mde[0][0]=' ';mde[0][1]='0';hd[0]=1;
for(int i=1;i<N;i++)
{
int p=i;mde[i][0]=' ';
while(p){mde[i][++hd[i]]='0'+p%10;p/=10;}
}
}inline void prit(int x){for(int i=hd[x];i>=0;i--)putchar(mde[x][i]);}
int a[N];int b[N];
inline void cons(int ad,int p,int k,int tot)//没啥好说的,就是直接分治就好了
{
if(k==1){for(int i=0;i<p;i++)prit(ad+i);putchar('\n');return;}//边界条件
int bl=tot/p;for(int i=0;i<tot;i+=bl)cons(ad+i,p,k-1,bl);//挨个递归
for(int i=0,id=0;i<tot;i+=bl,id++)a[id]=i;
for(int st=0;st<bl;st++)
{
b[0]=0;b[1]=st;for(int i=2;i<=p-1;i++)b[i]=(st+b[i-1])%bl;
for(int plus=0;plus<bl;plus++)//输出这一层的解
{for(int i=0;i<p;i++)prit(ad+a[i]+(b[i]+plus)%bl);putchar('\n');}
}
}int main(){pre();int p;int k;scanf("%d%d",&p,&k);printf("YES\n");cons(0,p,k,po(p,k));}
```