一年一度的Halloween又到了，在这里祝大家节日快乐~~~~
……

呃……有什么问题吗？
……
……

操！我又把OCT 31和DEC 25搞混了……

    
    octomatics.org是一个颠覆人类传统观念的网站，这个网站基本上就一个页面，介绍了一些八进制的应用，为推广和普及八进制的使用做了大量的工作。为了让人们在日常生活中使用八进制更加方便，网站上居然设计了一套像模像样的算术体系，包括数字书写、印刷体、运算法、计时法、时区划分，甚至有一个Flash八进制计算器。网站最后说：人们的习惯是一个很大的问题，我们已经深深地禁锢在十进制的世界里了……但今后的事情，谁知道呢？

    在各种文明的算术发展过程中，乘法运算的产生是很重要的一步。一个文明可以比较顺利地发展出计数方法和加减法运算，但要想创造一套简单可行的乘法运算方法却不那么容易。我们目前使用的乘法竖式计算看似简便，实际上这需要我们事先掌握九九乘法口诀表；考虑到这一点，这种竖式计算并不是完美的。我们即将看到，在数学的发展过程中，不同的文明创造出了哪些不同的乘法运算方法，其中有的运算法甚至可以完全抛弃乘法表。
    古巴比伦数学使用60进制，考古发现的一块古巴比伦泥板证实了这一点。这块泥板上有一个正方形，对角线上有四个数字1, 24, 51, 10。最初发现这块泥板时人们并不知道这是什么意思，后来某牛人惊讶地发现，如果把这些数字当作60进制的三位小数的话，得到的正好是单位正方形对角线长度的近似值：1 + 24/60 + 51/60^2 + 10/60^3 = 1.41421296296...  这说明古巴比伦已经掌握了勾股定理。60进制的使用为古巴比伦数学的乘法运算发展带来了很大的障碍，因为如果你要背59-59乘法口诀表的话，至少也得背1000多项，等你把它背完了后我期末论文估计都已经全写完了。另一项考古发现告诉了我们古巴比伦数学的乘法运算如何避免使用乘法表。考古学家们发现一些泥板上刻有60以内的平方表，利用公式ab = [(a+b)^2 - a^2 - b^2]/2 可以迅速查表得到ab的值。另一个公式则是ab = [(a+b)^2 - (a-b)^2]/4，这说明两个数相乘只需取它们的和平方与差平方的差，再两次取半即可。平方数的频繁使用很可能加速了古巴比伦人发现勾股定理的过程。
    古巴比伦数学把除以一个数看作是乘以它的倒数，利用倒数表可以很方便的实现这种算法。倒数表开头的一部分是这个样子：

2      0; 30
3      0; 20
4      0; 15
5      0; 12
6      0; 10
8      0; 7, 30
9      0; 6, 40
10     0; 6
12     0; 5
15     0; 4
16     0; 3, 45
18     0; 3, 20
20     0; 3
....    ....

    
    古巴比伦人很早就发现，1/7是一个无限小数，怎么除也除不完。古巴比伦的倒数表里所有的数都是精确的小数，它们（在60进制中）都是有限小数。碰到无限小数时，他们会用取近似值的方法来解决。例如，古巴比伦人会通过1/13 = 1*(1/13) = 7*(1/91) ≈ 7*(1/90) = 7*(40/3600) = (7*40)/3600 来计算1/13的值。那个40就是查倒数表查出来的。


    古埃及数学使用了完全不同的乘法运算法。它们的乘法运算不需要借助任何辅助用表。古埃及人注意到，任何一个数都可以表示为若干个不同的2的幂的和。因此，你需要做的仅仅是不断将1和乘数进行翻倍。看看古埃及人如何计算46乘以22：

  46 x 22 = 1012
   1   22
   2   44     44
   4   88   + 88
   8  176  + 176
  16  352
  32  704  + 704
          -------
            1012

    上面的演算中，左列是1不断翻倍的结果，右边是22不断翻倍的结果。选出左列的2, 4, 8, 32，它们的和正好就是被乘数46；那么把右列对应的数加起来就是乘法运算的最终结果。至于如何选出2, 4, 8, 32这四个数，一个简单的方法就是，不断选出左列里小于被乘数的数中最大的一个，然后当前被乘数减去它。比如，32是最大的数，用46-32后剩14；8是小于14的最大数，14-8后剩6；然后最大的小于6的数是4，6减去4后剩2，这样下来2+4+8+32正好就是被乘数46了。这其实就是二进制的经典应用，2, 4, 8, 32正好与46的二进制中的数字1一一对应。你可以在这里看到一些相关的东西。
    无独有偶，据说俄国农村曾产生过这样一种乘法算术法：将被乘数逐次减半，同时乘数依次加倍，那么找出所有左边的数是奇数的行，其右列的数的和就是答案。例如，下面的例子中，23, 11, 5和1都是奇数，于是右边对应的44, 88, 176和704的和就是乘法运算的结果。这个做法与古埃及的算术法完全一样，但看起来似乎更神奇一些。

  46 x 22 = 1012
  46   22
  23   44     44
  11   88   + 88
   5  176  + 176
   2  352
   1  704  + 704
          -------
            1012

做人要厚道
转贴请注明出处

Problem 1: Matrix67的情书（二）
    大家都知道，看一个数是否能被2整除只需要看它的个位能否被2整除即可。可是你想过为什么吗？这是因为10能被2整除，因此一个数10a+b能被2整除当且仅当b能被2整除。大家也知道，看一个数能否被3整除只需要看各位数之和是否能被3整除。这又是为什么呢？答案或多或少有些类似：因为10^n-1总能被3整除。2345可以写成2*(999+1) + 3*(99+1) + 4*(9+1) + 5，展开就是2*999+3*99+4*9 + 2+3+4+5。前面带了数字9的项肯定都能被3整除了，于是要看2345能否被3整除就只需要看2+3+4+5能否被3整除了。当然，这种技巧只能在10进制下使用，不过类似的结论可以推广到任意进制。
    注意到36是4的整数倍，而ZZZ...ZZ除以7总是得555...55。也就是说，判断一个36进制数能否被4整除只需要看它的个位，而一个36进制数能被7整除当且仅当各位数之和能被7整除。如果一个数同时能被4和7整除，那么这个数就一定能被28整除。于是问题转化为，有多少个连续句子满足各位数字和是7的倍数，同时最后一个数是4的倍数。这样，我们得到了一个O(n)的算法：用P[i]表示前若干个句子除以7的余数为i有多少种情况，扫描整篇文章并不断更新P数组。当某句话的最后一个字能被4整除时，假设以这句话结尾的前缀和除以7余x，则将此时P[x]的值累加到最后的输出结果中（两个前缀的数字和除以7余数相同，则较长的前缀多出来的部分一定整除7）。
    上述算法是我出这道题的本意，但比赛后我见到了其它各种各样新奇的算法。比如有人注意到36^n mod 28总是等于8，利用这个性质也可以构造出类似的线性算法来。还有人用动态规划（或者说递推）完美地解决了这个问题。我们用f[i,j]表示以句子i结束，除以28余数为j的文本片段有多少个；处理下一句话时我们需要对每一个不同的j进行一次扫描，把f[i-1,j]加进对应的f[i,j']中。最后输出所有的f[i,0]的总和即可。这个动态规划可以用滚动数组，因此它的空间同前面的算法一样也是常数的。
    如果你完全不知道我在说什么，你可以看看和进位制、同余相关的文章。另外，我之前还曾出过一道很类似的题(VOJ1090)，你可以对比着看一看。
    另外，非常抱歉地告诉大家，这道题的最后一个数据是错的。这个数据的第一个句子是一个空句子（感谢Ai.Freedom的提醒）。很多第一题只得了90分的好同志估计都是由于我的失误造成的，这里再次表示歉意。如果去掉最前面的那个问号，输出应该是19511110。

Problem 2: 送给MM的生日礼物
        
    我们用f[i,j,k]表示以第i行第j列的格子为右下角，边长为k的正方形是否符合要求。要想f[i,j,k]=True，首先必须满足f[i-1,j-1,k-2]为True（灰色部分满足要求）。另外，我们还需要保证图中两块蓝色区域相等，两块绿色区域相等，并且这四个区域自身还必须是对称的。由于动态规划的状态已经是三方的了，因此判断后面的这些条件必须在常数时间里完成。为此，我们可以在动态规划前进行以下6个预处理：

以同列不同行的两个格子(i,j)和(i',j)为右端点，同时向左扩展可以得到多长的相等区域
以同行不同列的两个格子(i,j)和(i,j')为最底端，同时向上扩展可以得到多长的相等区域
以格子(i,j)为中心，向左右扩展可以得到多长的对称区域
以格子(i,j)为中心，向上下扩展可以得到多长的对称区域
以两个横向相邻的格子(i,j-1)和(i,j)为中心，向左右扩展可以得到多长的对称区域
以两个纵向相邻的格子(i-1,j)和(i,j)为中心，向上下扩展可以得到多长的对称区域

    上面的每个预处理都可以在三方的时间里完成，动态规划的决策降到常数级别，因此总的复杂度还是三方。

    同样地，这也只是我出这道题的本意。我事先已经想到，这道题应该还有很多其它的算法，只是没想到会有那么多。一个比较容易想到的算法是，执行与上面相同的预处理后，枚举某个格子（或某个交叉点）为中心，向外一层一层地进行扩展。虽然这样的复杂度仍然是三方的，并且与前面的算法实质相同，但它的效率显然更高，因为你可以在无法再向外扩展时停止最里面的那个循环，继续枚举下一个中心点。
    同样是枚举正方形的中心点，只使用上面的后4个预处理也可以解决这个问题。我们可以在线性的时间内找出，以某个格子（或交叉点）为中心的最大的合法正方形。假如这个最大的正方形边长为k，这相当于我们同时找到了(k+1) div 2个正方形来。至于如何找到这个最大的正方形，还是留给大家思考吧。
    Cockhorse想到了一个非常巧妙的算法，预处理结束后它可以在常数时间内判断任一个给定的小正方形是否满足题目要求。用f[i,j,k]表示，以第i行中(i,j)及其右边相邻的k-1个格子（共k个格子）来作为底边，所能得到的左右对称的矩形其最大高度是多少。则当f[i,j+1,k-2]为True且(i,j)格与(i,j+k-1)格花色相等时f[i,j,k]=f[i-1,j,k]+1（否则f[i,j,k]=0）。同样地，再用g[i,j,k]表示以(j,i)..(j+k-1,i)作为右边界，使矩形上下对称的最大宽度。这样，判断任意一个正方形是否满足题目要求，只需要检查它的底边和右边能够产生的最大对称区域是否可以覆盖该正方形即可。
    当然，这道题目还有很多其它的算法，这里就不一一列举了。

Problem 3: 流言的传播
    给定一个图，把图中所有点构成的点集叫做U，另指定一个不等于全集的子集S，那么所有一个顶点在S里另一个顶点在U-S里的边就叫做S点集的“割边”，因为去掉所有这样的边后S集将孤立出来。这道题就是需要你找出一个边集E，使得不管S集是什么，对应的割边中权值最小的那一条一定在边集E中。这样的边集肯定是存在的，比如所有边构成的集合就是一个满足条件的边集。这道题希望你找到的边集E里所含的边尽可能的少。
    一个错误的贪心法是，去掉每个点的邻接边中权值最小的那一条。这种算法显然不对，比如下面就是一个鲜活的反例：

o-----o-----o-----o
   2     3     1

    在上图中，每个点的邻接边中权值最小的不是1就是2，这样的话中间那条边就被保留了下来，于是令S集为左边两个点（或右边两个点），割边仍然一条不少。很容易想到，要想让任意S集的割边中权值最小的被去掉，首先得保证边集E连通了所有的点，否则令S等于任一连通分量，边集E里都不会包含任何一条割边。这样，边集E至少要有n-1条边。
    考虑到最优解至少是n-1条边，这n-1条边必须连通所有的点，而所选边的权值都应该很小，于是想到最后的答案很可能就是最小生成树。现在假设我们已经选择了某些边，这些边形成了若干个连通分量。考虑所有连接两个不同的连通分量的边（两顶点不在同一连通分量的边）中权值最小的一条，那这条边必须要选，否则令S集为其中一个连通分量，题目条件就不能达到了。这不就是Kruskal算法吗？
    且慢，我们还没有证明，对任意一个S集，最小生成树都符合条件。证明其实很简单，假设权值最小的割边e不在最小生成树E中，添加割边e将形成一个回路。这条回路将从S集的某个点出发，经过e跑到U-S里，最后必须还要回到S集。回到S集必然要经过另一条割边e'，而显然e'>e（因为e是权值最小的割边，且题目说了没有权值相同的边），于是边集E+{e}-{e'}就成了更小的生成树。

Problem 4: 表白机器人
    第四题是整个模拟赛中最简单的题，它不需要你构造任何算法，你只需要按照题目意思进行模拟即可。和去年的NOIp一样，纯粹考编程能力的题目并没有放在第一道题的位置上。这提示大家拿到题目后要先看完所有的题，特别是看到最后一道题时千万别慌，很可能把它的衣服扒光了一看，发现它居然是一道赤裸裸的送分题。
    为了加快速度，先预处理出一个数组wall[i][j][k]，表示第i行第j列往k(1<=k<=4)方向上走是否走得通。然后枚举所有可能的命令序列，模拟机器人的行走过程，看它是否能到达终点。在模拟过程中，你需要用一个数组hash[i][j][k]表示机器人曾在序列的第k个命令后到达第i行第j列的位置，并在模拟过程中不断更新hash数组；当某一次命令后机器人还没走到右上角，而对应的hash值已经为True了，则机器人的行动将从这里开始循环，永远也到不了右上角了。
    虽然这道题不需要任何剪枝，但我还想再说一句。这道题有一个非常有趣的剪枝：命令序列的第一个指令只能是U或R，最后一个指令也只能是U或R。大家想想这是为什么。

    前面那篇日志里大家的讨论都很激烈，我很高兴。axgle的发言让我想起了这样一个非常有趣的例子。这是我很喜欢的一个科幻构想，我曾经在进位制讲解中引用过它。这里再次引用，表达我的另一个比较奇异的观点。

    语文和数学永远是最基础的两门学科，从小学开始我们就一直在接触它们。这两门学科教给人两种截然不同的思维方式，理性的思考和感性的思考。在众多学科中，可能只有语文是不需要逻辑思维的，大多数时候你只需要跟着你的感觉走。有时候我常常在想，如果人类文明没有发展出数学这门学科，只具有感性思维的能力，那么世界将会怎样。Robert J. Sawyer的科幻小说《Calculating God》里就构想了这样一个世界。小说中提到，人类有10根手指，因此发展出了满十进一的计数系统。10是前四个正整数的和，又是2和5的积，这样的进位制非常适合数学的发展。但小说中构想的一种外星生物却没有那么好的运气——它有23根手指。这种别扭的数字最多只能让人联想到乔丹和染色体，除此之外没有任何特性。这给这种生物的数学发展带来不可逾越的障碍。而事实上，这种生物恰好又没有发展数学的必要性。他就好像人类一样，对较小的物体个数具有直接感知的能力。人类可以直接感知的物体数量一般不超过6。也就是说，如果你眼前有3个，或者5个东西，你不需要数，看一眼就知道有多少个；但当你眼前出现的物体数目达到7个或者8个时，你就必须要数一数才知道个数了。而我们所说的生物面对的物体数目多达46个时仍然可以一眼分辨出多少来，数目超过46后就统称为“很多”了。46这个数字对于种族的生存已经完全足够了，他们在组建部落时总会保证部落里的个体数不超过这个数字。因此，这种生物不需要数数的能力，他们也就无须发展数学了。作为一种补偿，他们对事物的感知能力相当敏锐。他们甚至直接凭直觉感知到了相对论，因为他们的思维不受演绎逻辑的束缚。演绎逻辑思维正在限制我们的思想吗？或许，只具有感性思维的能力是一件好事。

    前几年有一个电影叫做Robot Stories，讲述有关机器人与人的四个独立的小故事。记得当时《科幻世界》上曾对这个电影有过介绍。下面这段视频是电影的片头动画，非常有意思：

。

3x12=36
2x12=24
1x12=12
0x12=18

    今天的最后一篇日志了，仍然是翻译的cut-the-knot。发完我就睡觉去了。

    这里已经有五种证明根号2是无理数的方法了。现在我们算是介绍第六种方法了。
    一个有限小数的平方绝对不可能变成整数，因为小数部分不可能消失。观察有限小数的小数部分最后一个数字你会发现结论是显然的，平方后它总会产生新的“最后一位”。
    下面证明，(n/m)^2不可能等于2。n/m不可能是整数，于是把它写成小数形式，而有限小数的平方不可能是整数。如果n/m不是有限小数的话，可以把它转换成另外的进制使得n/m是有限小数，因而上面的结论仍然成立。一个进制下的无限小数可能是另一个进制下的有限小数。比如，把分数n/m转化为m进制，得到的小数肯定是有限小数。