#P18277. (A + B) mod P

(A + B) mod P

(A + B) mod P

请为模一个固定素数的加法构造一个单隐藏层神经网络。

给定素数 pp,你需要选择神经元个数 nn,并输出两个实数矩阵 WinputW_{\mathrm{input}} 和 WoutputW_{\mathrm{output}},它们的大小都是 p×np\times n。矩阵的行从 00 到 p−1p-1 编号。

网络接收两个整数 a,ba,b(0≤a,b<p0\le a,b<p),按以下步骤计算:

  1. 将 WinputW_{\mathrm{input}} 的第 aa 行和第 bb 行逐项相加。
  2. 把结果中的每个负数改为 00,得到长度为 nn 的向量 MM。即 $M_j=\max(0,W_{\mathrm{input}}[a,j]+W_{\mathrm{input}}[b,j])$。
  3. 对每个候选结果 i=0,1,…,p−1i=0,1,\ldots,p-1,计算得分 $\mathrm{score}(i)=\sum_{j=1}^{n}M_jW_{\mathrm{output}}[i,j]$。得分最高的整数必须等于 (a+b) mod p(a+b)\bmod p。

你输出的两个矩阵必须对所有 p2p^2 个有序输入对 (a,b)(a,b) 都正确。正确类别必须是唯一的最高得分类别,不能依赖得分并列时的任意选择。

输入格式

唯一一行包含一个整数 pp。

输出格式

第一行输出一个整数 nn,满足 1≤n≤251\le n\le25。

接下来 pp 行输出 WinputW_{\mathrm{input}},每行包含 nn 个实数。

再接下来 pp 行以相同格式输出 WoutputW_{\mathrm{output}}。

所有矩阵元素的绝对值均不得超过 10001000。只要构造满足上述全部条件,就会被接受;不要求与样例或标准程序的矩阵相同。

数据范围

3≤p≤1003\le p\le100,且保证 pp 为素数。输入只有一组数据。

样例

3
4
2.5 3.0 -0.5 -3.0
-3.0 0.0 0.5 2.0
-0.5 0.5 -3.0 1.5
1.5 1.0 -2.0 2.5
-3.0 3.0 -1.0 2.0
-0.5 2.5 0.5 2.0

以 (1+2) mod 3(1+2)\bmod3 为例,先将输入矩阵第 11、22 行相加,得到 [−3.5,0.5,−2.5,3.5][-3.5,0.5,-2.5,3.5];将负数置零,得到 M=[0,0.5,0,3.5]M=[0,0.5,0,3.5]。

三个候选类别的得分依次为 9.259.25、8.58.5、8.258.25。类别 00 的得分最高,恰好等于 (1+2) mod 3(1+2)\bmod3。