#P16358. [2026年山东第二轮集训]随机算法

[2026年山东第二轮集训]随机算法

题目描述

在北京大学随机算法课程中,你将会遇到如下问题:

有一个大小为 nn 的集合 S={1,2,…,n}S=\{1,2,\ldots,n\} 以及一个二元运算 ∘\circ。你需要在 O(n2)O(n^2) 的时间内判定 ∘\circ 是否满足结合律,即判定是否对于所有 i,j,k∈Si,j,k\in S,均有

i∘(j∘k)=(i∘j)∘k.i\circ(j\circ k)=(i\circ j)\circ k.

这个问题对于大家来说还是太轻松了。但实际上,这道题的数据并不好造。如果不精心构造,很容易出现大量不满足结合律的三元组,导致随机检查也有极高概率给出正确判定。

因此,现在你的任务是为这道题构造数据。形式化地说,你需要处理 qq 组任务。对于第 xx 组任务,给定一个目标 cxc_x,你需要构造一个二元运算 ∘\circ,使得恰好有 cxc_x 个三元组满足结合律,即

$$\sum_{i\in S}\sum_{j\in S}\sum_{k\in S} \left[i\circ(j\circ k)=(i\circ j)\circ k\right]=c_x,$$

或者报告无解。

其中 [P][P] 表示:当命题 PP 为真时值为 11,否则值为 00。

输入格式

第一行包含两个整数 n,qn,q,分别表示集合大小和任务组数。

接下来 qq 行,每行包含一个整数 cxc_x,表示该组任务的目标。

输出格式

对于每组任务:

  • 第一行输出字符串 YES 或 NO,表示是否有解;
  • 若输出 YES,接下来输出一个 n×nn\times n 的矩阵描述运算 ∘\circ 的运算表,其中第 ii 行第 jj 列的整数表示 i∘ji\circ j 的值。

样例 1

输入

3 2
27
0

输出

YES
1 1 1
1 1 1
1 1 1
YES
2 2 2
1 1 3
2 2 2

数据范围

对于全部数据:

  • 1≤n≤641\le n\le64;
  • 1≤qn2≤1061\le qn^2\le10^6;
  • 0≤cx≤n30\le c_x\le n^3。

本题共 1010 个子任务,每个子任务 1010 分。

子任务

子任务编号 分值 特殊限制
1 10 n≤3n\le3
2 n≤8n\le8
3 保证所有 cx≤nc_x\le n
4 保证所有 cx≥n3−nc_x\ge n^3-n
5 保证所有 cx=0c_x=0
6 保证所有 cx≡0(modn)c_x\equiv0\pmod n
7 保证所有 cx≡0(modn2)c_x\equiv0\pmod{n^2}
8 保证输入文件为下发文件中的 random8.in
9 1≤qn3≤1061\le qn^3\le10^6
10 无特殊限制