P1737 [NOI2016] 旷野大计算 题解

· · 题解

我的一次伟大的尝试。

有一说一，这道题和游戏《A=B》好像。

题目指路

前言

让我们看看有哪些可用操作吧！

对三个扣分节点不予理睬，除了正常的输入输出、变量和常量加法、变量取反、乘或除以 2 的幂，还有一个我们不常见的东西—— 函数 s(x)。

既然题面都给了我们 s(x) 的图像，不如来研究一下它的性质。依照宇宙惯例，各位 dalao 可以跳过。

s(x)=\dfrac 1{1-e^{-x}}

【性质 1】

s(x)$ 过点 $(0,\frac 1 2)

证明：当 x=0 时，y=\frac 1 2。

证毕

【性质 2】

s(x)+s(-x)=1

证明：s(x)+s(-x)=\dfrac 1{1-e^{-x}}+\dfrac 1{1-e^x}=\dfrac{1-e^{-x}+1-e^{-x}}{1-e^{-x}-e^x+1}=1

证毕

【性质 3】

\lim\limits_{x\to\infty}s(x)=1,\lim\limits_{x\to-\infty}s(x)=0

证明：\lim\limits_{x\to\infty}s(x)=\frac{1}{1-0}=1

\lim\limits_{x\to-\infty}s(x)=\lim\limits_{x\to-\infty}\frac 1 x=0

证毕

事实上，函数 s(x) 被称为 Sigmoid 函数。因为它的值域为 [0,1]，且拥有性质 3，让它在神经网络中广泛运用。

最后碎碎念一下，题目里的输入有个小陷阱，只有 i,j 是前面的节点计算出的值，x,k 是常数可以直接带数进去。

下面，进入正题。

task 1

概况

输入：a,b

输出：-2a-2b

难度：受精卵

分析

-2a-2b=-2(a+b)=-(a+b)\times2^1

两行输入，一行加法，一行左移，一行取反，一行输出

代码

共 6 行

printf("I\n");
printf("I\n");
printf("+ 1 2\n");
printf("< 3 1\n");
printf("- 4\n");
printf("O 5\n");

task 2

概况

输入：a

输出：\dfrac 1{1+e^{17a}}

难度：满月

分析

一看这个式子，很像 s(x) 的式子。

这辈子不可能用乘法的，但怎么求 17a 呢？

17a=16a+a=a\times 2^4+a

所以 \dfrac 1{1+e^{17a}}=s(-(a\times 2^4+a))

一行输入，一行左移，一行加法，一行取反，一行 s(x)，一行输出。

代码

共 6 行

printf("I\n");
printf("< 1 4\n");
printf("+ 1 2\n");
printf("- 3\n");
printf("S 4\n");
printf("O 5\n");

task 3

概况

输入：a

输出：\left\{\begin{array}{ll} -1 & a<0 \\ 0 & a=0 \\ 1 & a>0 \end{array}\right.

难度：幼升小

分析

突然就难起来了。

虽然那个比较函数很诱人，但用一个四分没了。

回想上一题，那个函数 s(x) 只在那里有用，其它地方都用不上，好可怜。

……吗？

你看它的数据范围，整数部分一千位，小数部分九十位，谁没事会想写高精度呢？就连 spj 都只精确到小数点后九位。

再想想实数乘法法则，任何一个数乘以一个很大的正数，绝对值变得很大，符号不变。这个很大的整数很容易通过左移得到。

换句话说，我们要构造一个函数 f_3(x)，满足：

  1. \lim\limits_{x\to \infty} f_3(x)=1
  2. \lim\limits_{x\to -\infty} f_3(x)=-1
  3. f_3(0)=0

数感好的同学已经发现，f(x)=2s(x)-1，满足题意！

接下来就要决定那个非常非常大的正数取 2 的多少次方了。

列出不等式

\dfrac 1{1+e^{x_1}}\ge 1-5\times 10^{-91} \\ \dfrac 1{1+e^{x_2}}\le 4\times 10^{-91} \\ |x_1|\le 10^{1000} \\ |x_2|\le 10^{1000} \end{array}\right.

其中，x_1=10^{-9}\times 2^k,x_2=-10^{-9}\times 2^k，以及 k 为正整数。

借助某些工具，解得 k\ge 38。

当然，考试的时候可没有工具解。可以拿 python 跑二分。不过更好的方案是带一个较大的数进 k，比如 100。

综上，f_3(x)=\dfrac 2{1+e^{-a\times 2^{100}}}-1

顺带一提，f(x) 的图像长这样：

一行输入，一行左移，一行 s(x)，一行左移，一行偏移，一行输出。

代码

共 6 行

printf("I\n");
printf("< 1 100\n");
printf("S 2\n");
printf("< 3 1\n");
printf("C 4 -1\n");
printf("O 5\n");

task 4

概况

输入：a

输出：|a|

难度：小学奥数

分析

上面那一问的结果乘以 a，就是这一问的结果。但是我说过乘法节点这辈子不会用的。

让我们试图模仿一下。

-x & x<0\\ 0 & x=0\\ x & x>0 \end{array}\right.

直接求肯定不现实，我们考虑把它写成 x 加一个数的形式，就变成

x-2x & x<0\\ x+0 & x\ge 0 \end{array}\right.

也就是说，我们要求 f_4(x)=\left\{\begin{array}{ll} -2x & x<0\\ 0 & x\ge 0 \end{array}\right.

回头看看 s(x) 的图像，发现 x 在 0 附近很像一个一次函数。求个导会得出 x=0 处的切线解析式为 y=\frac 1 4 x+\frac 1 2。

至于如何缩小，我们可以使用 \lim\limits_{y\to\infty}s(\frac x y)，其中 y=2^q。

接下来，我们就需要把正负分开。上一问中，我们使用了 s(x) 的极限，这一问仍然考虑使用。

我们需要使用偏移，使结果对于自变量正负显著不同。

这个偏移肯定要用到 s(x)。

你看那个系数 2 和拟合一次函数的系数 \frac 1 4，一切都在告诉我们，用左右位移的指数差来构造。

这个偏移要在大于 0 时很大，在小于 0 时很小。好像 h=s(x\times 2^p)\times 2^q 正好是！

0 & x<0\\ 2^p & x\ge 0 \end{array}\right.

加在 s(x\times 2^{-q}) 上，有

s(x\times 2^{-q}) & x<0\\ 1 & x\ge 0 \end{array}\right.

再看导数拟合的一次函数，s(x\times 2^{-q})=\frac 1 4 x\times2^{-q}+\frac 1 2，也就是 x\times 2^{-(q+2)}+0.5。

在 x<0 时，f_4(x) 似乎就是上面那玩意减 0.5 乘 2^{q+3} 再取反的结果。拿 x>0 验证一下。

当 x>0 时，减 0.5 乘 2^{q+3} 再取反的结果为 -2^{q+2}，和要求不一样，怎么办？用偏移？

我们现在还拥有一个正负敏感的变量——h！只要取 p=q+2，再给上式加 p，完美解决！但是，0 呢？

由于 0 和正数处理方法一样，可以把 x 加上一个 spj 和输入精度以外、计算过程精度以内的数，也就是 10^{-10}，但为了保险，建议更小一些，比如 10^{-20}。

范围懒得算了，想算自己算吧，我就取 250 了。不放图了，画的时候电脑炸了。

代码

共 14 行

printf("I\n");
printf("C 1 0.00000000000000000001\n");
printf("< 2 250\n");
printf("S 3\n");
printf("< 4 250\n");
printf("> 1 248\n");
printf("+ 6 5\n");
printf("S 7\n");
printf("C 8 -0.5\n");
printf("< 9 251\n");
printf("- 10\n");
printf("+ 11 5\n");
printf("+ 12 1\n");
printf("O 13\n");

task 5

概况

输入：a_1,a_2,\cdots,a_{32}

输出：把 a_1,a_2,\cdots,a_{32} 从左到右看成一个二进制整数，高位在左，低位在右，输出该整数的值。

难度：小升初

分析

众所周知，小升初试题难度比小学奥数简单。

很简单，每个数按权值位移最后相加就完了。

但是，请不要为了循环美观去乘 2^0，会浪费一行。

输入三十二行，左移三十一行，相加三十一行，输出一行。

代码

共 95 行

对了，下文所有代码中 F(i,a,b) R(i,a,b) 分别指 for(int i=a;i<=b;++i) for(int i=a;i>=b;--i)。

F(i,1,32) printf("I\n");
F(i,1,31) printf("< %d %d\n",i,32-i);
printf("+ 63 32\n");
F(i,1,30) printf("+ %d %d\n",63+i,32+i);
printf("O 94\n");

task 6

概况

输入：a

输出：32 个整数，从高位到低位输出 a 的二进制表示（不足 32 位的在高位补 0）

难度：中考

分析

难度又加回来了，但也没 task 4 难。

二进制下的数 a 有个神奇的性质，若它至多有 t 位，则第 t 位为 [a\ge2^t]（方括号表示成立为 1，不成立为 0）。

然后，我们让 a'=a-2^t\times[a\ge2^t]，那么 a' 就是一个至多 t-1 位的数，可以重复上面操作。

问题就回到了比较大小。看看第三个点，不正是比较大小的问题吗？把 a 乘上 2^{50}，用 s(x) 就行。

再看每次用 s(x) 的位移，用分配律可以提出来，直接在开始时位移 a 就可以了。

然后是和 task 4 一样严峻的问题，如果相等减出 0 来，那值就成 0.5 了，误差不是一点半点。一样，偏移个 10^{-10}。

等等，你看循环里那么多偏移，为什么偏偏要专门在开头时浪费一行偏呢？我们每次偏移少偏一点，同样可以解决问题。因此，把偏移少偏个 2^{50}\times 10^{-10}\approx 112590。

最后，因为是正整数，最低位不用比，直接就是。

三十一次比较，每次六行，输入一行，左右偏移各一行，输出一行

解决！

代码

共 190 行

printf("I\n");
printf("< 1 50\n");
for(int i(3),j(31);j;--j,i+=6){
    char str[1001];
    sprintf(str,"%Lf",pow((long double)2.0,50+j)-112590);
    printf("C %d -%s\n",i-1,str);
    printf("S %d\n",i);
    printf("O %d\n",i+1);
    printf("- %d\n",i+2);
    printf("< %d %d\n",i+3,50+j);
    printf("+ %d %d\n",i+4,i-1); 
}
printf("> 188 50\n");
printf("O 189\n");

task 7

概况

输入：a,b

输出：a,b 按位异或的结果（下记为 \operatorname{xor}）

难度：高中

分析

task 5 和 task 6 的综合运用！

首先用 task 6 的代码转二进制，异或后再用 task 5 的代码转回来。

也就是说，目前首要目标为解决函数 f_7(x,y)，其中

0 & x=y\\ 1 & x\neq y \end{array}\right.

我相信你们老师或教练都讲过，异或是二进制下的不进位加法，不信你看：

0\operatorname{xor}0=0+0=0 0\operatorname{xor}1=1\operatorname{xor}0=0+1=1 1\operatorname{xor}1=(1+1)\bmod 2=0

自然而然想到加法。

但是，加法在 f_7(0,1) 或 f_7(1,0) 没问题，但对于 f_7(0,0) 和 f_7(1,1) 就完了，一个是 0 一个是 2。

结合 task 4 的经验，我们给 x+y 减一个数，得到 f_7(x,y)。

让我们记这个数为 f_7'(x,y)，则有

0 & x+y=0\\ 0 & x+y=1\\ 2 & x+y=2 \end{array}\right.

你看那个 2，是不是很不顺眼，把它除掉，只剩 0 和 1，函数 s(x) 又出来了。

再仔细看看，f_7'=2[x+y>1.5]！（1.5 可以是 1 到 2 间的任何一个数，为了方便取的。）

就是用 s(x) 实现比较！

解决！……了吗？

回到我刚才说的，异或是二进制下的不进位加法。这说明我们把二进制变回十进制时，可以优化。

但上面那种方法足以得到满分，这个优化留给读者思考。（其实是懒）

代码

共 603 行

printf("I\n");
printf("I\n");
printf("< 1 50\n");
for(int i(4),j(31);j;--j,i+=5){
    char str[1001];
    sprintf(str,"%Lf",pow((long double)2.0,50+j)-112590);
    printf("C %d -%s\n",i-1,str);
    printf("S %d\n",i);
    printf("- %d\n",i+1);
    printf("< %d %d\n",i+2,50+j);
    printf("+ %d %d\n",i+3,i-1); 
}
printf("> 158 50\n");
printf("< 2 50\n");
for(int i(161),j(31);j;--j,i+=5){
    char str[1001];
    sprintf(str,"%Lf",pow((long double)2.0,50+j)-112590);
    printf("C %d -%s\n",i-1,str);
    printf("S %d\n",i);
    printf("- %d\n",i+1);
    printf("< %d %d\n",i+2,50+j);
    printf("+ %d %d\n",i+3,i-1); 
}
printf("> 315 50\n");
for(int i(5),j(1);j<=31;++j,i+=5) printf("+ %d %d\n",i,i+157);
printf("+ 159 316\n");
for(int i(317),j(349);i<=348;j+=6,++i){
    printf("C %d -1.5\n",i);
    printf("< %d 50\n",j);
    printf("S %d\n",j+1);
    printf("< %d 1\n",j+2);
    printf("- %d\n",j+3);
    printf("+ %d %d\n",j+4,i);
}
for(int i(355),j(31);j>=1;--j,i+=6) printf("< %d %d\n",i,j);
for(int i(540),j(1);j<=31;++j,++i) printf("+ %d %d\n",i,i+31);
printf("O 602\n");

task 8

概况

输入：a

输出：\dfrac a{10}

难度：高中竞赛

分析

哎呀，终于不是二进制了。

看看输出，是一个关于 a 的正比例函数。

结合 task 4 肯定又要用到导数。我们要求出 s(x) 斜率为 0.1 的切线的切点坐标。

先来求个导，有

s'(x)=\dfrac{e^{-x}}{(1+e^{-x})^2}

这玩意是个连续函数，且最大值为 0.25，最小值无限接近 0。根据介值定理，方程 s'(x)=0.1 有解。

设这个解为 x_0。写出 x=x_0 处的切线，根据点斜式，有 y=s'(x_0)(x-x_0)+s(x_0)=0.1(x-x_0)+s(x_0)。

我们肯定可以继续用先缩小再放大的策略，即

\dfrac a{10}=0.1a+s(x_0)-s(x_0) =\dfrac{0.1a+s(x_0)-s(x_0)}{2^k}\times 2^k =(s(\dfrac a{2^k}+x_0)-s(x_0))\times 2^k

那么最后就是求解 x_0。

眼睛看上去，s'(x) 应该是偶函数，也就是说有两个解。为了方便，不妨令 x_0>0。

至于求解，八仙过海各显神通，checker、牛顿迭代、二分、计算器均可。

我用的计算器。化简式子得到 x_0=\ln(\sqrt{15}+4)\approx 2.0634370688955605467272811726201。

再用 checker 求得 s(x_0)。（太长了，见代码）

至于 k 就取 task 4 的 250。不知道为什么，我的计算器在 k>50 时会崩掉，就不放图了。

代码

共 7 行

printf("I\n");
printf("> 1 250\n");
printf("C 2 2.063437068895560546727281172620\n");
printf("S 3\n");
printf("C 4 -0.887298334620741688517926539978236773937633025540819832675154107295416657242528255923059519\n");
printf("< 5 250\n");
printf("O 6\n");

task 9

概况

输入：a_1,a_2,\cdots,a_{16}

输出：a_1,a_2,\cdots,a_{16} 升序排序后的结果

难度：高考

分析

其实也没那么难，综合性强而已。

排序无论如何都绕不开一个操作：比较并交换。

至于交换，由于每个节点只能被赋值一次，后面只能调用。因此，我们要用一个尽量不用中间变量的方法。

你看那个异或，603 行，不崩才怪。又因为肯定不会溢出，我们用加减法实现。

结合大小关系，我们可以得出下面这段交换代码：

h=a0+b0;
a1=h-min(a0,b0);
b1=h-a1;

也就是说，问题转化为实现 \min(a,b) 函数。它不同于 task 3，返回值为 a 或 b，而非 1 或 -1。

这似乎不是很好实现。让我们改写一下上面那段代码：

h=a0+b0;
a1=a0-min(a0-b0,0);
b1=h-a1;

为什么要改写成这种 \min(t,0) 的形式呢？回看 task 4，我们正好有 \min(t,0)=-0.5f_4(t)。

那这不就解决了吗？

题目给的操作不适合复杂的排序。让我们寻找原始的排序：冒泡排序。

最后模拟就完了。注意，常用的冒泡代码是倒着的，需要倒序输出。同样，因为节点的变化难以预测，可以用数组来记录节点号。

当然，你要用其他排序我也支持，但我不想再去思考其他怎么写，就用冒泡了。（甚至我觉得冒泡都不好写，看着题解调的。感谢 @da32s1da 题解的代码。）

代码

共 2312 行

short line[17]={};
F(i,1,16) printf("I\n"),line[i]=i;
for(int i(1),j(16);i<=15;++i) for(int k(i+1);k<=16;++k,j+=19){
    printf("- %d\n",line[k]);
    printf("+ %d %d\n",line[i],line[k]);
    printf("+ %d %d\n",line[i],j+1);
    printf("C %d 0.00000000000000000001\n",j+3);
    printf("< %d 250\n",j+4);
    printf("S %d\n",j+5);
    printf("< %d 250\n",j+6);
    printf("> %d 249\n",j+3);
    printf("+ %d %d\n",j+7,j+8);
    printf("S %d\n",j+9);
    printf("< %d 1\n",j+10);
    printf("- %d\n",j+6);
    printf("+ %d %d\n",j+11,j+12);
    printf("C %d -1\n",j+13);
    printf("< %d 250\n",j+14);
    printf("- %d\n",j+15);
    printf("+ %d %d\n",line[i],j+16),line[i]=j+17;
    printf("- %d\n",line[i]);
    printf("+ %d %d\n",j+2,j+18),line[k]=j+19;
}
R(i,16,1) printf("O %d\n",line[i]);

task 10

概况

输入：a,b,m

输出：ab\bmod m

难度：大学

分析

大学比高考要更摆烂些。

好像绕不开乘法了呢，又不能用乘法节点，怎么办？

回到乘法在小学中的定义，乘法是连加的简记。

一个一个加肯定不行，b 个节点不是闹着玩的。

在历年来的 NOI 中，考察过这样的一个知识点——龟速乘。它适用于两数相乘取模但会溢出的情况。思想与快速幂类似，二进制拆分，按权相乘，最后相加。

例如：3\times 5\bmod 2=3\times(2^2+2^0)\bmod 2

=3\times 2^2\bmod 2+3\times 2^0\bmod 2 =12\bmod 2+3\bmod 2=0+1=1

不过这里一千位，肯定不会溢出，因此取模放在最后进行，先着重处理乘法。

在二进制拆分后，根据二进制该位是 0 或 1 进行位移。现在问题就是计算 x\times y，其中 x\in\{0,1\}。

写成分段函数，有 x\times y=\left\{\begin{array}{ll} 0 & x=0\\ y & x=1 \end{array}\right.

这玩意是不是除了范围又很像 f_4(x)？把 x 偏移 -0.5，就又可以用 -0.5f_4(x) 计算了。所以说小学奥数是世界的尽头。

那么就剩取模了。取模可以用减法实现，但一个个减又太浪费了。这时就可以再用二进制。

为了减少取反次数，先取反 $ab$，每次加，最后再取反回来，就解决了。 听说还可以用泰勒展开或康托展开，但对于像我一样的初中蒟蒻，龟速乘无疑是最佳方式。~~（虽然我会泰勒展开）~~ 但是实现的时候，我带的 $250$ 莫名奇妙用不了了，改成了 @da32s1da [题解](https://www.luogu.com.cn/blog/da32s1da/wu-p1737-post)中的 $180$，许多细节也要微调，请自行查看代码。 至此，本题完结！ ### 代码 共 $1381$ 行 ```cpp printf("I\n"); printf("I\n"); printf("I\n"); printf("> 1 180\n"); printf("< 2 180\n"); for(int i(5),j(31);j;--j,i+=12){ char str[1001]; sprintf(str,"%Lf",pow((long double)2.0,18 str[25]=str[26]=str[27]='0'; printf("C %d -%s\n",j==31?5:i-7,str); printf("S %d\n",i+1); printf("- %d\n",i+2); printf("< %d %d\n",i+3,180+j); printf("+ %d %d\n",i+4,j==31?5:i-7); printf("C %d -1\n",i+2); printf("< %d 250\n",i+6); printf("+ %d %d\n",4,i+7); printf("S %d\n",i+8); printf("< %d 1\n",i+9); printf("+ %d %d\n",i+10,i+3); printf("< %d %d\n",i+11,181+j); } printf("> 370 180\n"); printf("C 378 -1\n"); printf("< 379 180\n"); printf("+ 4 380\n"); printf("S 381\n"); printf("< 382 1\n"); printf("- 378\n"); printf("+ 384 383\n"); printf("< 385 181\n"); for(int i(17),j(1);j<=31;++j,i+=12) printf("+ printf("> 3 200\n"); printf("C 417 0.5\n"); for(int j(63),i(419);j>=0;--j,i+=15){ printf("< 3 %d\n",j); printf("- %d\n",i+1); printf("+ %d %d\n",i+2,i); printf("< %d 500\n",i+3); printf("S %d\n",i+4); printf("C %d -1\n",i+5); printf("< %d 500\n",i+6); printf("+ %d 418\n",i+7); printf("S %d\n",i+8); printf("< %d 1\n",i+9); printf("- %d\n",i+5); printf("+ %d %d\n",i+11,i+10); printf("< %d %d\n",i+12,j+201); printf("- %d\n",i+13); printf("+ %d %d\n",i+14,i); } printf("C 1379 -0.5\n"); printf("O 1380\n"); ``` ## 后记 这篇跨越了一个月的题解终于完成了！ 主要的运用是 $s(x)$ 的极限。 不得不说是真的容易崩，还是感谢前面几位 dalao 的题解和代码，不然我也搞不出来。 完整代码不放了，自己动手拼一拼。代码是真的难调，参数是真的难选。 原题解不是太长，就是太短，才有了这篇不长不短的题解。 完结撒花 awa~