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

· · 题解

神仙构造题……

膜神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个数组啦，于是我们的分治法成功奏效这题就做完了……

听说这题卡输出于是写了个快速输出……速度惊人

#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));}