Puzzleup网站上每年都会举行一次数学谜题比赛。07年的比赛将于8月1日开始（由于时差原因，我们这里可能要晚一些）。比赛共进行20个星期，每个星期网站上会发布一道数学谜题，题目涉及代数、几何、概率、组合数学等各个领域。你需要把你得到的答案提交上去。题目描述十分简单，人人都懂；但真要想起来却没那么容易。比赛结束后，前十名将收到Puzzleup的证书，想来是一件很酷的事情。
    我参加了06年的比赛，可以负责任地告诉大家题目会是你喜欢的类型。遗憾的是由于各种原因，最后我没有坚持做到比赛结束。这里我翻译一下去年比赛的前5期题目，让感兴趣的同学先看看Puzzleup的题目类型。

1. 有五张红色的牌和五张蓝色的牌，分别从1到5编号。把这10张牌排成一圈，同时满足下面两个条件的排列方案有多少种？
     - 任两张相邻的牌颜色不同
     - 任两张相邻的牌编号不同
   如果这个问题是问的3张红牌和3张蓝牌，那么答案应该是12。

2. 沿着对角线把一个八边形分割为三角形共有多少种方法？
   如果这个问题问的是五边形，答案应该是5。

3. 老师叫学生们写下他们曾经去过的国家。每个学生独立地在自己的答卷上写下国家的名字。所有学生的答卷上共包含10个国家的名字，每张答卷都不相同，任两张答卷至少含有一个相同的名字。学生最多有多少个？

4. 16枚硬币摆成4x4的正方形。另一枚硬币贴着它们转一圈最后回到原位。请问这枚硬币自转了多少圈？

5. 在标准的8x8棋盘上摆放棋子，有多少种放法使得每个格子的相邻格子中正好有奇数个棋子？
   注意：相邻格子是指上下左右相邻，角上相邻的格子和格子自身不算。

更多的题目可以在这里找到

    ArtOfProblemSolving.com是一个数学社区网站。网站里有10个展示数学解题艺术的flash动画，每次打开首页时侧边栏会随机选择一个播放。这10个flash用简陋的动画证明了10个经典结论，整个证明过程只有动画演示，没有用一句话。这些经典证明哪些你已经见过？哪些你一看就懂？你最喜欢哪个？

http://www.matrix67.com/blogimage/2007072901.swf
http://www.matrix67.com/blogimage/2007072902.swf
http://www.matrix67.com/blogimage/2007072903.swf
http://www.matrix67.com/blogimage/2007072904.swf
http://www.matrix67.com/blogimage/2007072905.swf
http://www.matrix67.com/blogimage/2007072906.swf
http://www.matrix67.com/blogimage/2007072907.swf
http://www.matrix67.com/blogimage/2007072908.swf
http://www.matrix67.com/blogimage/2007072909.swf
http://www.matrix67.com/blogimage/2007072910.swf

    你是否有过这样的经历：在电视上看到一部快要演完的电影，很想知道电影的名字；或者你想重温小时候看过的某个电影时却忘了那个电影的名字。如果你还记得电影里的经典台词，Google一下原话或许可以找到那部电影；如果你还记得演员或者导演的名字，imdb上查一下人名也可以很快找到你要的电影。但如果你什么都忘记了，只依稀记得一些情节的话，咋办呢？除了“人肉搜索”外，这篇日志还将告诉你另一种根据电影内容查电影名的有效方法——使用imdb的Keywords功能。近两年来imdb的变化很大，加入了很多web 2.0元素，比如Keywords说穿了就是一个电影的Tag。imdb的用户可以给每个电影写多个Keywords，然后大家就可以根据Keywords进行分类查询。我已经多次用这种方法找到了我需要的电影名字，这里写出来分享一下。
    我一直以为我看过的第一部美剧是The X Files，直到前几天突然想起我在六七岁时看过一个单元剧。这部剧集大概讲述一家人不知为何（没看第一集）到了一个荒无人烟的陌生世界里。然后呢，我还记得的细节就只有这么几个：那个世界里恐龙，这家人有一个DV，有一集开头他们在打篮球，有一集里涉及火山和岩浆，还有一集他们错过了回去的机会。让人郁闷的是一天晚上我出去玩没看成，落掉的那一集恰好是最后一集。
    记得那只恐龙几乎在每一集都有出现，是整部剧集的特点之一。于是，我在imdb的搜索里填入dinosaur，搜索类型选择Keywords；或者干脆直接在地址栏输入www.imdb.com/keyword/dinosaur。接下来，你会在屏幕左边看到相关的标签云，在右边可以看到从Jurassic Park到Night at the Museum等200多个和恐龙相关的电影列表。imdb的Keywords很全面，如果你要找的电影不是特别冷僻的话，通常不必担心这个Keyword没被它收录。下面的例子告诉你一个电影的Keywords有多全面：如果你不是对Sin City特别熟悉的话，你怎么也想不明白为什么Sin City也有dinosaur这个关键字。
    接下来，我们可以通过选择左边的下属标签来缩小范围。一个比较显眼的下属标签是Kids And Family (47)，这说明Keywords里既含有dinosaur又含有Kids And Family的电影有47个。出现大致同义的Keyword时，我们通常选择包含电影更多的那个，因为包含电影更多的标签表示这个词更常用。因此这里我们没有选择family标签。点击这个标签后电影列表缩短到了47项。我是88年生的，如果我七岁左右看的这个电视剧，那这部剧集应该在95年以前就有了；这部电影的画面也不像是70年以前的电影。按照日期对电影排序后，可以看到70年到95年的这类电影只有十几个。在imdb中，为了把电视剧和电影区别开来，电视剧名一律用双引号标注。在十几个电影，标有双引号的不足7个。哪一个名字的电视剧更像是在讲述另一个世界里的历险故事呢？91年的这个电视剧名字不错，"Land of the Lost"。进去一看简介，果然就是它：The Porter family, Tom, Kevin, and Annie get sucked into a prehistoric alternative world while taking a family vacation...
    最后YouTube找到Land of the Lost的片头，放出来给大家看看。有人看过这部剧集吗？



做人要厚道
转贴要注明出处哦~~

    我们把一个边长为2的正方形划分成4个小正方形，每个小正方形里作一个内切圆，然后在原来的大正方形中间作一个同时外切于这4个圆的小圆（红色标注）。我们把这个小圆叫做“中心圆”。你怎么来求这个中心圆的半径？
    仔细观察其中一个小正方形，思路就出来了：红色的中心圆变成了一个90度扇形，它的中心位于单位正方形的一角，并且外切于直径为1的圆。可以看到扇形半径加上圆的半径等于单位正方形对角线的一半，这样我们就得出，中心圆的半径等于(sqrt(2)-1)/2。
    对于一个立方体同样如此。我们把立方体切成8个小立方体，得到的8个球体中间夹住的那个中心球半径就应该为(sqrt(3)-1)/2。你会发现一个惊人的事实，在超立方体中，位于16个四维球体间的中心球半径为(sqrt(4)-1)/2 = 1/2，它竟然与那16个小球一样大。真正可怕的事情发生在九维立方体中，此时的九维中心球半径为(sqrt(9)-1)/2 = 1，竟然内切于最初的九维立方体！而到了十维空间后，中心球的直径将超过十维立方体的边长，这个中心球将突破立方体的边界！被围在里面的中心球居然比原来的N维立方体还大，这显然违反了大多数人的直觉；如果你能想象出这个画面来，你就牛B了。科幻小说中把对十维空间的感知能力作为文明发达程度的标准，除了一些相关的宇宙模型外，这可能也是其中一个原因吧。

    下面分享的是我自己写的三个代码，里面有些题目也是我自己出的。这些代码都是在我的Pascal时代写的，恕不提供C语言了。代码写得并不好，我只是想告诉大家位运算在实战中的应用，包括了搜索和状态压缩DP方面的题目。其实大家可以在网上找到更多用位运算优化的题目，这里整理出一些自己写的代码，只是为了原创系列文章的完整性。这一系列文章到这里就结束了，希望大家能有所收获。
    Matrix67原创，转贴请注明出处。

Problem : 费解的开关

题目来源
    06年NOIp模拟赛（一） by Matrix67 第四题

问题描述
    你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
    我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态

10111
01101
10111
10000
11011

    在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011

    再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011

    给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。

输入格式
    第一行有一个正整数n，代表数据中共有n个待解决的游戏初始状态。
    以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
    对于30%的数据，n<=5；
    对于100%的数据，n<=500。

输出格式
    输出数据一共有n行，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
    对于某一个游戏初始状态，若6步以内无法使所有灯变亮，请输出“-1”。

样例输入
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

样例输出
3
2
-1

程序代码
const
   BigPrime=3214567;
   MaxStep=6;
type
   pointer=^rec;
   rec=record
         v:longint;
         step:integer;
         next:pointer;
       end;

var
   total:longint;
   hash:array[0..BigPrime-1]of pointer;
   q:array[1..400000]of rec;

function update(a:longint;p:integer):longint;
begin
   a:=a xor (1 shl p);
   if p mod 5<>0 then a:=a xor (1 shl (p-1));
   if (p+1) mod 5<>0 then a:=a xor (1 shl (p+1));
   if p<20 then a:=a xor (1 shl (p+5));
   if p>4 then a:=a xor (1 shl (p-5));
   exit(a);
end;

function find(a:longint;step:integer):boolean;
var
   now:pointer;
begin
   now:=hash[a mod BigPrime];
   while now<>nil do
   begin
      if now^.v=a then exit(true);
      now:=now^.next;
   end;

   new(now);
   now^.v:=a;
   now^.step:=step;
   now^.next:=hash[a mod BigPrime];
   hash[a mod BigPrime]:=now;
   total:=total+1;
   exit(false);
end;

procedure solve;
var
   p:integer;
   close:longint=0;
   open:longint=1;
begin
   find(1 shl 25-1,0);
   q[1].v:=1 shl 25-1;
   q[1].step:=0;
   repeat
      inc(close);
      for p:=0 to 24 do
         if not find(update(q[close].v,p),q[close].step+1) and (q[close].step+1<MaxStep) then
         begin
            open:=open+1;
            q[open].v:=update(q[close].v,p);
            q[open].step:=q[close].step+1;
         end;
   until close>=open;
end;

procedure print(a:longint);
var
   now:pointer;
begin
   now:=hash[a mod BigPrime];
   while now<>nil do
   begin
      if now^.v=a then
      begin
         writeln(now^.step);
         exit;
      end;
      now:=now^.next;
   end;
   writeln(-1);
end;

procedure main;
var
   ch:char;
   i,j,n:integer;
   t:longint;
begin
   readln(n);
   for i:=1 to n do
   begin
      t:=0;
      for j:=1 to 25 do
      begin
         read(ch);
         t:=t*2+ord(ch)-48;
         if j mod 5=0 then readln;
      end;
      print(t);
      if i<n then readln;
   end;
end;

begin
   solve;
   main;
end.

=======================  性感的分割线  =======================

Problem : garden / 和MM逛花园

题目来源
    07年Matrix67生日邀请赛第四题

问题描述
    花园设计强调，简单就是美。Matrix67常去的花园有着非常简单的布局：花园的所有景点的位置都是“对齐”了的，这些景点可以看作是平面坐标上的格点。相邻的景点之间有小路相连，这些小路全部平行于坐标轴。景点和小路组成了一个“不完整的网格”。
    一个典型的花园布局如左图所示。花园布局在6行4列的网格上，花园的16个景点的位置用红色标注在了图中。黑色线条表示景点间的小路，其余灰色部分实际并不存在。
        

    Matrix67 的生日那天，他要带着他的MM在花园里游玩。Matrix67不会带MM两次经过同一个景点，因此每个景点最多被游览一次。他和他的MM边走边聊，他们是如此的投入以致于他们从不会“主动地拐弯”。也就是说，除非前方已没有景点或是前方的景点已经访问过，否则他们会一直往前走下去。当前方景点不存在或已游览过时，Matrix67会带MM另选一个方向继续前进。由于景点个数有限，访问过的景点将越来越多，迟早会出现不能再走的情况（即四个方向上的相邻景点都访问过了），此时他们将结束花园的游览。Matrix67希望知道以这种方式游览花园是否有可能遍历所有的景点。Matrix67可以选择从任意一个景点开始游览，以任意一个景点结束。
    在上图所示的花园布局中，一种可能的游览方式如右图所示。这种浏览方式从(1,2)出发，以(2,4)结束，经过每个景点恰好一次。

输入格式
    第一行输入两个用空格隔开的正整数m和n，表示花园被布局在m行n列的网格上。
    以下m行每行n个字符，字符“0”表示该位置没有景点，字符“1”表示对应位置有景点。这些数字之间没有空格。

输出格式
    你的程序需要寻找满足“不主动拐弯”性质且遍历所有景点的游览路线。
    如果没有这样的游览路线，请输出一行“Impossible”（不带引号，注意大小写）。
    如果存在游览路线，请依次输出你的方案中访问的景点的坐标，每行输出一个。坐标的表示格式为“(x,y)”，代表第x行第y列。
    如果有多种方案，你只需要输出其中一种即可。评测系统可以判断你的方案的正确性。

样例输入
6 4
1100
1001
1111
1100
1110
1110

样例输出
(1,2)
(1,1)
(2,1)
(3,1)
(4,1)
(5,1)
(6,1)
(6,2)
(6,3)
(5,3)
(5,2)
(4,2)
(3,2)
(3,3)
(3,4)
(2,4)

数据规模
    对于30%的数据，n,m<=5；
    对于100%的数据，n,m<=10。

程序代码：
program garden;

const
   dir:array[1..4,1..2]of integer=
     ((1,0),(0,1),(-1,0),(0,-1));

type
   arr=array[1..10]of integer;
   rec=record x,y:integer;end;

var
   map:array[0..11,0..11]of boolean;
   ans:array[1..100]of rec;
   n,m,max:integer;
   step:integer=1;
   state:arr;

procedure readp;
var
   i,j:integer;
   ch:char;
begin
   readln(m,n);
   for i:=1 to n do
   begin
      for j:=1 to m do
      begin
         read(ch);
         map[i,j]:=(ch='1');
         inc(max,ord( map[i,j] ))
      end;
   readln;
   end;
end;

procedure writep;
var
   i:integer;
begin
   for i:=1 to step do
      writeln( '(' , ans[i].x , ',' , ans[i].y , ')' );
end;

procedure solve(x,y:integer);
var
   tx,ty,d:integer;
   step_cache:integer;
   state_cache:arr;
begin
   step_cache:=step;
   state_cache:=state;
   if step=max then
   begin
      writep;
      exit;
   end;

   for d:=1 to 4 do
   begin
      tx:=x+dir[d,1];
      ty:=y+dir[d,2];
      while map[tx,ty] and ( not state[tx] and(1 shl (ty-1) )>0) do
      begin
         inc(step);
         ans[step].x:=tx;
         ans[step].y:=ty;
         state[tx]:=state[tx] or ( 1 shl (ty-1) );
         tx:=tx+dir[d,1];
         ty:=ty+dir[d,2];
      end;

      tx:=tx-dir[d,1];
      ty:=ty-dir[d,2];
      if (tx<>x) or (ty<>y) then solve(tx,ty);
      state:=state_cache;
      step:=step_cache;
   end;
end;

{====main====}
var
   i,j:integer;
begin
   assign(input,'garden.in');
   reset(input);
   assign(output,'garden.out');
   rewrite(output);

   readp;
   for i:=1 to n do
   for j:=1 to m do
     if map[i,j] then
     begin
        ans[1].x:=i;
        ans[1].y:=j;
        state[i]:=1 shl (j-1);
        solve(i,j);
        state[i]:=0;
     end;

   close(input);
   close(output);
end.

=======================  性感的分割线  =======================

Problem : cowfood / 玉米地

题目来源
    USACO月赛

问题描述
    农夫约翰购买了一处肥沃的矩形牧场，分成M*N(1<=M<=12; 1<=N<=12)个格子。他想在那里的一些格子中种植美味的玉米。遗憾的是，有些格子区域的土地是贫瘠的，不能耕种。
    精明的约翰知道奶牛们进食时不喜欢和别的牛相邻，所以一旦在一个格子中种植玉米，那么他就不会在相邻的格子中种植，即没有两个被选中的格子拥有公共边。他还没有最终确定哪些格子要选择种植玉米。
    作为一个思想开明的人，农夫约翰希望考虑所有可行的选择格子种植方案。由于太开明，他还考虑一个格子都不选择的种植方案！请帮助农夫约翰确定种植方案总数。

输入格式:
    第一行：两个用空格分隔的整数M和N
    第二行到第M+1行：第i+1行描述牧场第i行每个格子的情况，N个用空格分隔的整数，表示这个格子是否可以种植（1表示肥沃的、适合种植，0表示贫瘠的、不可种植）

输出格式
    一个整数，农夫约翰可选择的方案总数除以 100,000,000 的余数

样例输入
2 3
1 1 1
0 1 0

样例输出
9

样例说明

    给可以种植玉米的格子编号：
      1 2 3
        4

    只种一个格子的方案有四种(1,2,3或4)，种植两个格子的方案有三种(13,14或34)，种植三个格子的方案有一种(134)，还有一种什么格子都不种。
    4+3+1+1=9。

数据规模
    对于30%的数据，N,M<=4；
    对于100%的数据，N,M<=12。

程序代码：
program cowfood;

const
   d=100000000;
   MaxN=12;

var
   f:array[0..MaxN,1..2000]of longint;
   w:array[1..2000,1..2000]of boolean;
   st:array[0..2000]of integer;
   map:array[0..MaxN]of integer;
   m,n:integer;

function Impossible(a:integer):boolean;
var
   i:integer;
   flag:boolean=false;
begin
   for i:=1 to MaxN do
   begin
      if flag and (a and 1=1) then exit(true);
      flag:=(a and 1=1);
      a:=a shr 1;
   end;
   exit(false);
end;

function Conflict(a,b:integer):boolean;
var
   i:integer;
begin
   for i:=1 to MaxN do
   begin
      if (a and 1=1) and (b and 1=1) then exit(true);
      a:=a shr 1;
      b:=b shr 1;
   end;
   exit(false);
end;

function CanPlace(a,b:integer):boolean;
begin
   exit(a or b=b);
end;

procedure FindSt;
var
   i:integer;
begin
   for i:=0 to 1 shl MaxN-1 do
      if not Impossible(i) then
      begin
         inc(st[0]);
         st[st[0]]:=i;
      end;
end;

procedure Init;
var
   i,j:integer;
begin
   for i:=1 to st[0] do
   for j:=i to st[0] do
      if not Conflict(st[i],st[j]) then
      begin
         w[i,j]:=true;
         w[j,i]:=true;
      end;
end;

procedure Readp;
var
   i,j,t,v:integer;
begin
   readln(m,n);
   for i:=1 to m do
   begin
      v:=0;
      for j:=1 to n do
      begin
         read(t);
         v:=v*2+t;
      end;
      map[i]:=v;
      readln;
   end;
end;

procedure Solve;
var
   i,j,k:integer;
begin
   f[0,1]:=1;
   map[0]:=1 shl n-1;
   for i:=1 to m do
   for j:=1 to st[0] do
      if not CanPlace(st[j],map[i]) then f[i,j]:=-1 else
        for k:=1 to st[0] do if (f[i-1,k]<>-1) and w[j,k] then
           f[i,j]:=(f[i,j]+f[i-1,k]) mod d;
end;

procedure Writep;
var
   j:integer;
   ans:longint=0;
begin
   for j:=1 to st[0] do
      if f[m,j]<>-1 then ans:=(ans+f[m,j]) mod d;
   writeln(ans);
end;

begin
   assign(input,'cowfood.in');
   reset(input);
   assign(output,'cowfood.out');
   rewrite(output);

   FindSt;
   Init;
   Readp;
   Solve;
   Writep;

   close(input);
   close(output);
end.

    相信大家曾见过不少“图中有多少张脸”、“你能找出多少匹马”一类的图片。但我敢保证，这里给大家看的是“Spot the object”类图片里最有趣的一个（至少我认为是这样）。图画中有隐藏的老虎，看谁先找出来。噢，当然，不是明显的那只。这里我不公布答案，因为知道了答案后你会后悔自己没有看出来。因此，大家评论时也不要透露答案。我刚看到的觉得很好玩，火星了的话甘愿被B4。

今天我们来看两个稍微复杂一点的例子。

n皇后问题位运算版
    n皇后问题是啥我就不说了吧，学编程的肯定都见过。下面的十多行代码是n皇后问题的一个高效位运算程序，看到过的人都夸它牛。初始时，upperlim:=(1 shl n)-1。主程序调用test(0,0,0)后sum的值就是n皇后总的解数。拿这个去交USACO，0.3s，暴爽。
procedure test(row,ld,rd:longint);
var
      pos,p:longint;
begin

{ 1}  if row<>upperlim then
{ 2}  begin
{ 3}     pos:=upperlim and not (row or ld or rd);
{ 4}     while pos<>0 do
{ 5}     begin
{ 6}        p:=pos and -pos;
{ 7}        pos:=pos-p;
{ 8}        test(row+p,(ld+p)shl 1,(rd+p)shr 1);
{ 9}     end;
{10}  end
{11}  else inc(sum);

end;
    乍一看似乎完全摸不着头脑，实际上整个程序是非常容易理解的。这里还是建议大家自己单步运行一探究竟，实在没研究出来再看下面的解说。

  
    和普通算法一样，这是一个递归过程，程序一行一行地寻找可以放皇后的地方。过程带三个参数，row、ld和rd，分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。我们以6x6的棋盘为例，看看程序是怎么工作的。假设现在已经递归到第四层，前三层放的子已经标在左图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置，位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来，得到该行所有的禁位，取反后就得到所有可以放的位置（用pos来表示）。前面说过-a相当于not a + 1，这里的代码第6行就相当于pos and (not pos + 1)，其结果是取出最右边的那个1。这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用test过程。注意递归调用时三个参数的变化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。最后，如果递归到某个时候发现row=111111了，说明六个皇后全放进去了，此时程序从第1行跳到第11行，找到的解的个数加一。

    ~~~~====~~~~=====   华丽的分割线   =====~~~~====~~~~

Gray码
    假如我有4个潜在的GF，我需要决定最终到底和谁在一起。一个简单的办法就是，依次和每个MM交往一段时间，最后选择给我带来的“满意度”最大的MM。但看了dd牛的理论后，事情开始变得复杂了：我可以选择和多个MM在一起。这样，需要考核的状态变成了2^4=16种（当然包括0000这一状态，因为我有可能是玻璃）。现在的问题就是，我应该用什么顺序来遍历这16种状态呢？
    传统的做法是，用二进制数的顺序来遍历所有可能的组合。也就是说，我需要以0000->0001->0010->0011->0100->...->1111这样的顺序对每种状态进行测试。这个顺序很不科学，很多时候状态的转移都很耗时。比如从0111到1000时我需要暂时甩掉当前所有的3个MM，然后去把第4个MM。同时改变所有MM与我的关系是一件何等巨大的工程啊。因此，我希望知道，是否有一种方法可以使得，从没有MM这一状态出发，每次只改变我和一个MM的关系（追或者甩），15次操作后恰好遍历完所有可能的组合（最终状态不一定是1111）。大家自己先试一试看行不行。
    解决这个问题的方法很巧妙。我们来说明，假如我们已经知道了n=2时的合法遍历顺序，我们如何得到n=3的遍历顺序。显然，n=2的遍历顺序如下：

00
01
11
10

    你可能已经想到了如何把上面的遍历顺序扩展到n=3的情况。n=3时一共有8种状态，其中前面4个把n=2的遍历顺序照搬下来，然后把它们对称翻折下去并在最前面加上1作为后面4个状态：

000
001
011
010  ↑
--------
110  ↓
111
101
100

    用这种方法得到的遍历顺序显然符合要求。首先，上面8个状态恰好是n=3时的所有8种组合，因为它们是在n=2的全部四种组合的基础上考虑选不选第3个元素所得到的。然后我们看到，后面一半的状态应该和前面一半一样满足“相邻状态间仅一位不同”的限制，而“镜面”处则是最前面那一位数不同。再次翻折三阶遍历顺序，我们就得到了刚才的问题的答案：

0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

    这种遍历顺序作为一种编码方式存在，叫做Gray码（写个中文让蜘蛛来抓：格雷码）。它的应用范围很广。比如，n阶的Gray码相当于在n维立方体上的Hamilton回路，因为沿着立方体上的边走一步，n维坐标中只会有一个值改变。再比如，Gray码和Hanoi塔问题等价。Gray码改变的是第几个数，Hanoi塔就该移动哪个盘子。比如，3阶的Gray码每次改变的元素所在位置依次为1-2-1-3-1-2-1，这正好是3阶Hanoi塔每次移动盘子编号。如果我们可以快速求出Gray码的第n个数是多少，我们就可以输出任意步数后Hanoi塔的移动步骤。现在我告诉你，Gray码的第n个数（从0算起）是n xor (n shr 1)，你能想出来这是为什么吗？先自己想想吧。

    下面我们把二进制数和Gray码都写在下面，可以看到左边的数异或自身右移的结果就等于右边的数。

二进制数   Gray码
   000       000
   001       001
   010       011
   011       010
   100       110
   101       111
   110       101
   111       100

    从二进制数的角度看，“镜像”位置上的数即是对原数进行not运算后的结果。比如，第3个数010和倒数第3个数101的每一位都正好相反。假设这两个数分别为x和y，那么x xor (x shr 1)和y xor (y shr 1)的结果只有一点不同：后者的首位是1，前者的首位是0。而这正好是Gray码的生成方法。这就说明了，Gray码的第n个数确实是n xor (n shr 1)。

    今年四月份mashuo给我看了这道题，是二维意义上的Gray码。题目大意是说，把0到2^(n+m)-1的数写成2^n * 2^m的矩阵，使得位置相邻两数的二进制表示只有一位之差。答案其实很简单，所有数都是由m位的Gray码和n位Gray码拼接而成，需要用左移操作和or运算完成。完整的代码如下：
var
   x,y,m,n,u:longint;
begin
   readln(m,n);
   for x:=0 to 1 shl m-1 do begin
      u:=(x xor (x shr 1)) shl n; //输出数的左边是一个m位的Gray码
      for y:=0 to 1 shl n-1 do
         write(u or (y xor (y shr 1)),' '); //并上一个n位Gray码
      writeln;
   end;
end.

Matrix67原创
转贴请注明出处

Bless All NOIers...

现在大家差不多该上路了吧，祝大家考前一路顺利，考场上超常发挥，评测时RP++，最后满载而归！
现在闲的厉害，不知道大家报名前或考完后有没有自发组织什么活动的，有的话我想过来玩玩，瞻仰一下各位大牛
刚才没事看了一下NOI笔试题，有些题目笑死我了……