自动搬运

查看原文

来自洛谷，原作者为

	shadowice1984 これが勘違いでも、これが勘違いでも

搬运于2025-08-24 22:08:55，当前版本为作者最后更新于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$个数组啦，于是我们的分治法成功奏效这题就做完了……

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

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