还有几分钟就2007了
大家新年快乐

    去年的这个时候，SciFi频道也推出了一个迷你剧，The Triangle，讲述百慕大三角的故事。三集，一集一个半小时；不分季，放完拉到，决不回归。看完第一集，我大呼媲美24，但后面两集越来越乱，前面的悬念感觉一点也没有了。待我真正看完The Triangle，也并不觉得咋样，很多东西完全是为了需要瞎搞的，完全不顾整个剧情的连续性和严密性。
    今年SciFi的The Lost Room同样如此。仿佛这年头和Lost沾边的东西都很俏，不少东西要么取个带Lost字眼的名字搞点玄乎的，要么模仿Lost的Flash Back。第一集相当精彩，后面开始就乱来了。我本来还期望着有一个史诗级的全新时空观解释，结果最后什么能量要守恒，The Object必须要转移之类的东西完全不能自圆其说。总之，这个剧看起来是由激动，到期待，到失望。
    全剧结尾我居然猜到了（那人果然把钥匙扔进去了），看美剧有史以来的第一次。

    还有好玩的。注意到了吗，这迷你剧上居然打了Windows Live的标！

    刚才在网上搜我们班一个MM的名字，找到了这里：http://cmtj.xingming.net/log3/file/张.htm
    如果你真的进了这个页面，你的机器至少假死2秒。这个网页包含了数不清的张某（当然也有我要查的MM的名字）。我来了兴致，Ctrl+F找了一下这个页面里有没有我认识的其它姓张的人的名字（找了Simon，找了ZJ；ZPR？ZPR就是我说的那个MM），果然找到了，一找一个准。这他妈的是个什么页面？全中国的张姓人名都在里面吗？我试着进http://cmtj.xingming.net/log3/file/顾.htm（这个页面打开得比较快，毕竟顾姓没张姓那么多），果然也找到了我的名字。
    这是什么东西呢？答案就在cmtj.xingming.net。这是一个看名字给人算命的地方，很多人都在这里输过自己的名字（当然也有没有输自己名字的，比如输“猪八戒”、“本拉登”、“马加爵”或“笨蛋”什么的）。所有被输入过的名字都按姓氏记录在上面的那些网页里。因此，这无疑是一个巨大无比的人名库。你可以看看你的名字是否别人曾经用过或者想用。dd的名字在里面，SY的名字也在（当然要排除是自己到xingming.net测试过的可能），至于xg嘛，王.htm我根本不敢打开来，否则机器起码假死一分钟。当然，也有名字取得独特在里面找不到的。比如，小猫的名字就不在http://cmtj.xingming.net/log3/file/尚.htm里面。（小猫高兴了？）

    还有，xingming.net算名字算得如何呢？呵呵，别提了，那玩意儿把我年龄都算错了。摘录一段关于爱情的：

　　您出生于1988年5月16日，今年19岁(以下资料仅供参考)：

爱情特质：
　　认真的活，认真的爱，最喜心有灵犀一点通，最怕辛苦经营一场空 。
爱情物语：
　　等一下啦！我再观察一下、再想一下，我们到底能不能成为情人？
爱 情 观：
　　为 了 爱 而 奉 献 身 心
理想情人：
　　金 牛 座 -- 安定环境能让你有幸福的感觉  

　　舒畅的心情,宽裕的空间让你心满意足,平静安定的环境才能带给你幸福,所以心平气和稳重的人与你最相配.除外表温和外,不鲁莽行事,成熟踏实类型是你的最爱,能与你共享知性话题,才具备完美情人条件.

             ** 你 的 理 想 对 象 是 诚 实 稳 重 型 **
纯情指数：
　　☆☆☆☆
      金牛座的纯情指数跟白羊座完全不同，他们喜欢从等待和观察中慢慢的累积感情，需要比较长的时间。但一旦感情稳定下来后，也比较不会变心。
魅　　力：
　　稳重和乐於照顾别人的特质，总是散发让人安心和依赖的魅力加上他的随和愉悦特质，更是无尽的魅力泉源。
一见钟情：
　　金牛天性谨慎而踏实,虽然对於爱情抱有幻想,不过对「一见钟情」却是很少发生o因为他并不渴望这种刺激,宁愿一步一步慢慢来,用心 品味“细水长流”的爱情滋味o

    而且中西结合呢！你看完生辰八字后马上可以看到星座运势……寒，还有这样的……

你现在所看到的日志已于07年7月重新整理，下面是新的位运算系列文章目录。

位运算简介及实用技巧（一）：基础篇
位运算简介及实用技巧（二）：进阶篇(1)
位运算简介及实用技巧（三）：进阶篇(2)
位运算简介及实用技巧（四）：实战篇

    我们年级有许多漂亮的MM。一班有7个左右吧，二班大概有4个，三班最多，16个，四班最可怜，一个漂亮的MM都没有，五班据说有1个。如果用一个函数“f(班级)=漂亮MM的个数”，那么我们可以把上述信息表示成：f(1)=7,f(2)=4,f(3)=16,f(4)=0,f(5)=1,等等。
    生成函数（也有叫做“母函数”的，但是我觉得母函数不太好听）是说，构造这么一个多项式函数g(x)，使得x的n次方系数为f(n)。于是，上面的f函数的生成函数g(x)=7x+4x^2+16x^3+x^5+...。这就是传说中的生成函数了。关键是，这个有什么用呢？一会儿要慢慢说。我敢打赌这绝对会是我写过的最长的一篇文章。

    生成函数最绝妙的是，某些生成函数可以化简为一个很简单的函数。也就是说，不一定每个生成函数都是用一长串多项式来表示的。比如，这个函数f(n)=1 （n当然是属于自然数的），它的生成函数就应该是g(x)=1+x+x^2+x^3+x^4+...（每一项都是一，即使n=0时也有x^0系数为1，所以有常数项）。再仔细一看，这就是一个有无穷多项的等比数列求和嘛。如果-1<x<1，那么g(x)就等于1/(1-x)了。在研究生成函数时，我们都假设级数收敛，因为生成函数的x没有实际意义，我们可以任意取值。于是，我们就说，f(n)=1的生成函数是g(x)=1/(1-x)。

    我们举一个例子说明，一些具有实际意义的组合问题也可以用像这样简单的一个函数全部表示出来。
    考虑这个问题：从二班选n个MM出来有多少种选法。学过简单的排列与组合的同学都知道，答案就是C(4,n)。也就是说。从n=0开始，问题的答案分别是1,4,6,4,1,0,0,0,...（从4个MM中选出4个以上的人来方案数当然为0喽）。那么它的生成函数g(x)就应该是g(x)=1+4x+6x^2+4x^3+x^4。这不就是……二项式展开吗？于是，g(x)=(1+x)^4。
    你或许应该知道，(1+x)^k=C(k,0)x^0+C(k,1)x^1+...+C(k,k)x^k；但你或许不知道，即使k为负数和小数的时候，也有类似的结论：(1+x)^k=C(k,0)x^0+C(k,1)x^1+...+C(k,k)x^k+C(k,k+1)x^(k+1)+C(k,k+2)x^(k+2)+...（一直加到无穷；式子看着很别扭，自己写到草稿纸上吧，毕竟这里输入数学式子很麻烦）。其中，广义的组合数C(k,i)就等于k(k-1)(k-2)...(k-i+1)/i!，比如C(4,6)=4*3*2*1*0*(-1)/6!=0，再比如C(-1.4,2)=(-1.4)*(-2.4)/2!=1.68。后面这个就叫做牛顿二项式定理。当k为整数时，所有i>k时的C(k,i)中分子都要“越过”0这一项，因此后面C(k,k+1),C(k,k+2)之类的都为0了，与我们的经典二项式定理结论相同；不同的是，牛顿二项式定理中的指数k可以是任意实数。

    我们再举一个例子说明一些更复杂的生成函数。n=x1+x2+x3+...+xk有多少个非负整数解？这道题是学排列与组合的经典例题了。把每组解的每个数都加1，就变成n+k=x1+x2+x3+...+xk的正整数解的个数了。教材上或许会出现这么一个难听的名字叫“隔板法”：把n+k个东西排成一排，在n+k-1个空格中插入k-1个“隔板”。答案我们总是知道的，就是C(n+k-1,k-1)。它就等于C(n+k-1,n)。它关于n的生成函数是g(x)=1/(1-x)^k。这个生成函数是怎么来的呢？其实，它就是(1-x)的-k次方。把(1-x)^(-k)按照刚才的牛顿二项式展开，我们就得到了x^n的系数恰好是C(n+k-1,n)，因为C(-k,n)*(-x)^n=[(-1)^n*C(n+k-1,n)]*[(-1)^n*x^n]=C(n+k-1,n)x^n。这里看晕了不要紧，后文有另一种方法可以推导出一模一样的公式。事实上，我们有一个纯组合数学的更简单的解释方法。因为我们刚才的几何级数1+x+x^2+x^3+x^4+...=1/(1-x)，那么(1+x+x^2+x^3+x^4+...)^k就等于1/(1-x)^k。仔细想想k个(1+x+x^2+x^3+x^4+...)相乘是什么意思。(1+x+x^2+x^3+x^4+...)^k的展开式中，n次项的系数就是我们的答案，因为它的这个系数是由原式完全展开后k个指数加起来恰好等于n的项合并起来得到的。

    现在我们引用《组合数学》上暴经典的一个例题。很多书上都会有这类题。
    我们要从苹果、香蕉、橘子和梨中拿一些水果出来，要求苹果只能拿偶数个，香蕉的个数要是5的倍数，橘子最多拿4个，梨要么不拿，要么只能拿一个。问按这样的要求拿n个水果的方案数。
    结合刚才的k个(1+x+x^2+x^3+x^4+...)相乘，我们也可以算出这个问题的生成函数。

g(x)=(1+x^2+x^4+...)(1+x^5+x^10+..)(1+x+x^2+x^3+x^4)(1+x)
    =[1/(1-x^2)]*[1/(1-x^5)]*[(1-x^5)/(1-x)]*(1+x) （前两个分别是公比为2和5的几何级数，
                                                     第三个嘛，(1+x+x^2+x^3+x^4)*(1-x)不就是1-x^5了吗）
    =1/(1-x)^2   （约分，把一大半都约掉了）
    =(1-x)^(-2)=C(1,0)+C(2,1)x+C(3,2)x^2+C(4,3)x^3...   （参见刚才对1/(1-x)^k的展开）
    =1+2x+3x^2+4x^3+5x^4+....

    于是，拿n个水果有n+1种方法。我们利用生成函数，完全使用代数手段得到了答案！
    如果你对1/(1-x)^k的展开还不熟悉，我们这里再介绍一个更加简单和精妙的手段来解释1/(1-x)^2=1+2x+3x^2+4x^3+5x^4+....。
    1/(1-x)=1+x+x^2+x^3+x^4+...是前面说过的。我们对这个式子等号两边同时求导数。于是，1/(1-x)^2=1+2x+3x^2+4x^3+5x^4+....。一步就得到了我们所需要的东西！不断地再求导数，我们同样可以得到刚才用复杂的牛顿二项式定理得到的那个结论（自己试试吧）。生成函数还有很多其它的处理手段，比如等式两边同时乘以、除以常数（相当于等式右边每一项乘以、除以常数），等式两边同时乘以、除以一个x（相当于等式右边的系数“移一位”），以及求微分积分等。神奇的生成函数啊。
    我们用两种方法得到了这样一个公式：1/(1-x)^n=1+C(n,1)x^1+C(n+1,2)x^2+C(n+2,3)x^3+...+C(n+k-1,k)x^k+...。这个公式非常有用，是把一个生成函数还原为数列的武器。而且还是核武器。


    接下来我们要演示如何使用生成函数求出Fibonacci数列的通项公式。
    Fibonacci数列是这样一个递推数列：f(n)=f(n-1)+f(n-2)。现在我们需要求出它的生成函数g(x)。g(x)应该是一个这样的函数：
    g(x)=x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+...
    等式两边同时乘以x，我们得到：
    x*g(x)=x^2+x^3+2x^4+3x^5+5x^6+8x^7+...
    就像我们前面说过的一样，这相当于等式右边的所有系数向右移动了一位。
    现在我们把前面的式子和后面的式子相加，我们得到：
    g(x)+x*g(x)=x+2x^2+3x^3+5x^4+8x^5+...
    把这最后一个式子和第一个式子好好对比一下。如果第一个式子的系数往左边移动一位，然后把多余的“1”去掉，就变成了最后一个式子了。由于递推函数的性质，我们神奇地得到了：g(x)+x*g(x)=g(x)/x-1。也就是说，g(x)*x^2+g(x)*x-g(x)=-x。把左边的g(x)提出来，我们有：g(x)(x^2+x-1)=-x。于是，我们得到了g(x)=x/(1-x-x^2)。
    现在的任务是要把x/(1-x-x^2)还原成通项公式。这不是我们刚才的1/(1-x)^n的形式，我们要把它变成这种形式。我们发现，1-x-x^2=[1-(1-√5)x/2]*[1-(1+√5)x/2] （(1-√5)/2和(1+√5)/2是怎么算出来的？显然它们应该是x^2-x-1=0的两个根）。那么x/(1-x-x^2)一定能表示成?/[1-(1-√5)x/2]+?/[1-(1+√5)x/2]的形式（再次抱歉，输入数学公式很麻烦，将就看吧）。这是一定可以的，因为适当的?的取值可以让两个分式通分以后分子加起来恰好为一个x。?取值应该是多少呢？假设前面一个?是c1，后面那个是c2，那么通分以后分子为c1*[1-(1+√5)x/2]+c2*[1-(1-√5)x/2]，它恰好等于x。我们得到这样两个式子：常数项c1+c2=0，以及一次项-c1*(1+√5)/2-c2*(1-√5)/2=1。这两个式子足够我们解出c1和c2的准确值。你就不用解了，我用的Mathematica 5.0。解出来c1=-1/√5，c2=1/√5。你不信的话你去解吧。现在，我们把x/(1-x-x^2)变成了-(1/√5)/[1-(1-√5)x/2] + (1/√5)/[1-(1+√5)x/2]。我们已经知道了1/[1-(1-√5)x/2]的背后是以(1-√5)/2为公比的等比数列，1/[1-(1+√5)x/2]所表示的数列公比为(1+√5)/2。那么，各乘以一个常数，再相加，我们就得到了Fibonacci数列的通项公式：f(n)=-(1/√5)*[(1-√5)/2]^n + (1/√5)*[(1+√5)/2]^n。或许你会问，这么复杂的式子啊，还有根号，Fibonacci数列不都是整数吗？神奇的是，这个充满根号的式子对于任何一个自然数n得到的都是整数。熟悉用特征方程解线性递推方程的同学应该知道，以上过程实质上和找特征根求解没有区别。事实上，用上面所说的方法，我们可以求出任何一个线性齐次递推方程的通项公式。什么叫做线性齐次递推呢？就是这样的递推方程：f(n)等于多少个f(n-1)加上多少个f(n-2)加上多少个f(n-3)等等。Fibonacci数列的递推关系就是线性齐次递推关系。

    我们最后看一个例子。我们介绍硬币兑换问题：我有1分、2分和5分面值的硬币。请问凑出n分钱有多少种方法。想一下刚才的水果，我们不难得到这个问题的生成函数：g(x)=(1+x+x^2+x^3+...)(1+x^2+x^4+...)(1+x^5+x^10+..)=1/[(1-x)(1-x^2)(1-x^5)]。现在，我们需要把它变成通项公式。我们的步骤同刚才的步骤完全相同。我们把(1-x)(1-x^2)(1-x^5)展开，得到1-x-x^2+x^3-x^5+x^6+x^7-x^8。我们求出-1+x+x^2-x^3+x^5-x^6-x^7+x^8=0的解，得到了以下8个解：-1,1,1,1,-(-1)^(1/5),(-1)^(2/5),-(-1)^(3/5),(-1)^(4/5)。这个不是我解出来的，我还是用的Mathematica 5.0。不是我不想解，而是我根本不会解这个8次方程。这也是为什么信息学会涉及这些东西的原因：次数稍微一高，只好交给计算机解决了。于是，(1-x)(1-x^2)(1-x^5)=(1+x)(1-x)^3(1+(-1)^(1/5) x)()()() （省略不写了）。注意那个(1-x)^3。由于等根的出现，我们不得不把(1-x)^3所包含的(1-x)和(1-x)^2因子写进一会儿的分母里，不然会导致解不出合适的c来。你可以看到很多虚数。不过没关系，这些虚数同样参与运算，就像刚才的根式一样不会影响到最后结果的有理性。然后，我们像刚才一样求出常数满足1/(1-x)(1-x^2)(1-x^5)=c1/()+c2/(1-x)+c3/(1-x)^2+c4/(1-x)^3...+c8/()。这个解太复杂了，我用Mathematica解了几分钟，打印出了起码几十KB的式子。虽然复杂，但我确实是得到了通项公式。你有兴趣的话可以尝试用Mathematica解决一下1/[(1-x)(1-x^3)] （只有1分和3分的硬币）。解c的值时可以用SolveAlways[]函数。你可以亲眼见到，一个四五行的充满虚数的式子最后总是得到正确的整数答案。

    生成函数还有很多东西，推导Catalan数列啊，指数生成函数啊，之类的。我有空再说吧，已经5000多个字了。

    huyichen一直在问那道题。很显然，那道题目和上面的兑换硬币有些联系。事实上，很多与它类似的题目都和生成函数有关。但那个题却没有什么可以利用生成函数的地方（或许我没想到吧）。或许每个max的值有什么方法用生成函数解出来，但整个题目是不大可能用生成函数解决的。
    近来有个帖子问一道“DP天牛”题目的。那个题目也是这样，很多与它类似的题目都和DP有关，但那道题却不大可能动规。我总觉得它可以归约到装箱问题（考虑体积关系，最少要几个箱子才能把物品放完），而后者貌似属于NPC。或许我错了吧，现在没事就在研究理论的东西，很久没有想过OI题了，这方面的能力已经开始退化了。

Matrix67原创
做人要厚道，转贴请注明出处

    看了这么久的美剧，第一次发生我正在追的美剧被cut的。
    Day Break，讲述一个类似于《一日囚》的故事。可以说是相当精彩，tv.com打的9.1分，各集的分数像当初Heroes一样疯狂上涨。结果，再好的剧也要看收视率的脸色。悲哀的是，Day Break是连续剧，不是单元剧。才上映6集，第一季还有7集没放呢，竟然就不允许放了。伤心啊，我想看结局呢，本来还期待着大转折的。连续剧放到一半不放了，美国佬的电视台居然有这样的事情。

    还有，1087好好听啊！

    终于搬完家了，累死我了。
    一年多了到底写了多少篇日志，我从来没数过，貌似MSN Space也不提供这个统计数据。搬家后一看，150篇。不错。你能想到这150篇日志是怎么从MSN Space那里搬过来的吗？告诉你，我没写程序，我没用RSS，我什么都没用——我是手工Copy过来的！包括每一个图片，包括字体大小和颜色，都是人工转移和设置的（因此，不可避免的会出一些错，大家发现了要及时告诉我哦）。原因很简单，我还要增加tags，还要为每篇日志评分。
    本来想听dd的话用WordPress的，但是国内的服务器支持MySQL的少得可怜（都装的Win系统，直接提供asp+access），51.net的php版本又太低了；国外的虚拟主机好是好，但是有些地方很麻烦。最后还是选择了asp的PJBlog。不管用哪个软件，至少都比MSN Space好，MSN Space从来没有更新过什么有实际意义的东西不说，输出的接口也不提供。现在管理Blog就方便了，想再转移也很轻松，因为我可以访问我的数据库，很多东西都是透明的了。透明是一件好事。要是MM的衣服是透明的该多好啊！
    自己安家搞Blog有很多好处。比如，现在大家可以不用注册直接留言，我也安装了留言板插件。界面更好看，很多东西都可以自定义。这些东西MSN Space没有也不能怪人家微软，毕竟别人的数据量太大，在数据结构上不大可能升级（这也是一直无法改分类名称的原因，而我的MSN Space上分类名称太丑了）。当初MSN Space建成后的日志结构现在已经很落后（比如当时还没出现tag），而以后微软又没办法动它，最后只有让它越来越跟不上时代。
    主页上同步更新关于信息学的东西，特别放上了一些附件供大家下载。大家不要一窝蜂去下，不然我的流量超了，哭是哭不出来的。

    近来有很多问该看什么书的。我说一下个人意见（仅代表个人意见）。大家可以按照这样的顺序来阅读这些书（时间足够的话）：

    《算法导论》
    《数据结构与算法分析——C语言描述》
    《组合数学》

    这三本书必看，都是机械工业出版社出版的，翻译质量嘛——尽管有些别扭（翻译的东西都这样），但肯定看得懂。
    第一本的中译本是才出版的，比原来那个盗版的要好得多。
    第二本是Mark Allen Weiss写的，第二版。
    第三本是Richard A.Brualdi写的，第四版。
    如果你英文好的话，最好看原版。
    有人会问我为什么喜欢国外的教材。这是因为，国外的教材各个章节安排得很好，体系性更强，看起来更轻松（保证你能看懂），而且更具有启发性。这些教材的习题安排得很好，绝对是可以经过独立思考想出来的题目。和国内很多教材扔出一大堆概念和公式不同，阅读国外教材是循序渐进的一个学习过程。

    以下两本书的话，有兴趣就看吧。
    《离散数学》，第六版，Richard Johnsonbaugh，电子工业出版社。
    《How to Ace Calculus: The Streetwise Guide》系列，中译本叫做“微积分之XXXX”，湖南科学技术出版社。当成看小说吧，很有意思，是我见过的最不像教材的教材了。

    最后需要看的是刘汝佳和黄亮的《算法艺术与信息学竞赛》。这里面有很多概念上的讲解是错误的，但是题目讲解的资源很丰富。当前面的书看完了后，拿最后这一本当作题库来实战演练吧。书里的概念讲解部分就不必看了，直接消化里面的例题，一道一道地消化。第三部分的计算几何可以仔细学习一下，因为这部分内容之前的书好像涵盖得不多。

    还有，选择什么样的题库。个人首推USACO。大家可以自己了解一下这个与众不同的OJ，它基本上是一个“个人的教练”，并不参与网络排名。你大概需要话半年的时间完成所有的题目。做USACO需要你的认真态度和耐心。千万别看中译和别人的解答。整个USACO的任务完成之后，你基本上就无敌了。