题解 P5271 【OwenOwl 不学车也不删库】

shadowice1984

2019-03-23 21:45:44

Solution

神仙构造题…… 膜神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));} ```