组合数学
以下所写的来源于原书第五版《组合数学》，以及各大网站，博客论坛，我就不一一注明出处了，因为本就无意用于商业，只是供参考学习而已的。
幻方问题：
幻方：指一个幻方行、列、主对角线及泛对角线各数之和均相等。
一：对于奇数阶的幻方，有如下规律：
首先把1放在第一行的正中间，其后面的数按照自然顺序放置在从左下方到右上方的一条对角线上，并做如下修正：
（1）当到达第一行时，下一个整数的放置位置是：它所处的最后一行，所处的列是紧跟前一个整数所处的列的后面一列。
（2）当到达最右边的一列时，下一个整数的放置位置是：他所处的列是最左边的列（即第一列），它所处的行是紧跟前一个整数所处行的上一行。
（3）当达到一个已经填上数的方格或者已经达到幻方的右上角时，下一个整数放置的位置是填写上一个整数的直接下方。
二：对于阶数为4*n形时，有如下规律：
采用对称元素交换法。
首先把数1到n×n按从上至下，从左到右顺序填入矩阵
然后将方阵的所有4×4子方阵中的两对角线上位置的数关于方阵中心，作对称交换，即a(i,j）与a(n+1-i,n+1-j）交换，所有其它位置上的数不变。
（或者将对角线不变，其它位置对称交换也可）
三：对于阶数为4*n+2形时，有如下方法：
把大方阵4*n+2分解为4个奇数(2m+1阶）子方阵。
然后每个子方阵按照奇数阶求幻方的方法去求。
相互重叠的圆：
说到相互重叠，指的是每一对圆相交于两个不同点（不允许不相交和相切的圆）。
说到普通位置，指的是不存在只有一个共同点的三个圆。这n个圆在平面上构成若干区域，我们的目标是找出不同区域的数量。
设
为构建的区域数，显然H1=2（圆内和圆外），H2=4……。
咱解决这类问题，可以用递推的方式，也就是从当前n-1个圆变到n个圆时出现的区域变化。
假设已经构建好了Hn-1个区域，接着加入第n个圆使得在普通位置下有n个相互重叠的圆。那么即是前n-1个圆的每一个圆都与第n个圆相交出两个点，因为这些圆都处于普通位置上，所以我们得到2*（n-1）个不同点，这2*（n-1）个点把第n个圆分割成2*（n-1）条弧，每条弧都创建出额外2*（n-1)个区域，因此Hn满足下面的关系：
Hn=Hn-1+2*(n-1） （n>=2)
Hn=Hn-2+2*(n-2)+2*(n-1)
...
Hn=H1+2*(1)+2*(2)+...+2*(n-2)+2*(n-1)
=2+2*n*(n-1)/2=n^2-n+2 (n>=2)
Nim游戏：
这游戏的规则：
（1）玩家轮番出场（我们称第一个取子的玩家为A，而第二个玩家为B）。
（2）当轮到一个玩家取子时，他们都要从选择的硬币堆中至少取走一枚硬币。（这位玩家也可以把所硬币都取走，于是剩下一个空堆，这时它 ”退出”。）
当所有都硬币堆都空了的时候，游戏结束。走最后一步玩家，即取走最后一枚硬币的玩家获胜。
举个特殊例子：
有两堆硬币，分别为8,5。聪明取子步骤为8,5->5,5->5,2->2,2->0,2->0,0。
最后直接推到一般：
各大堆大小分别为N1，N2，……Nk的一般的Nim取子游戏。将每一个数Ni表示为其二进制数（数的位数相等，不等时在前面补0）：
N1 = as…a1a0
N2 = bs…b1b0
……
Nk = ms…m1m0
如果每一种大小的子堆的个数都是偶数，我们就称Nim取子游戏是平衡的，而对应位相加是偶数的称为平衡位，否则称为非平衡位。因此，Nim取子游戏是平衡的，当且仅当：
as + bs + … + ms 是偶数
……
a1 + b1 + … + m1 是偶数
a0 + b0 + … + m0是偶数
于是，我们就能得出获胜策略：
游戏人A能够在非平衡取子游戏中取胜，而游戏人B能够在平衡的取子游戏中取胜。
我们以一个两堆硬币的Nim取子游戏作为试验。设游戏开始时游戏处于非平衡状态。这样，游戏人A就能通过一种取子方式使得他取子后留给游戏人II的是一个平衡状态下的游戏，接着无论游戏人B如何取子，再留给游戏人A的一定是一个非平衡状态游戏，如此反复进行，当游戏人B在最后一次平衡状态下取子后，游戏人A便能一次性取走所有的硬币而获胜。而如果游戏开始时游戏牌平衡状态，那根据上述方式取子，最终游戏人B能获胜。
下面应用此获胜策略来考虑4-堆的Nim取子游戏。其中各堆的大小分别为7，9，12，15枚硬币。用二进制表示各数分别为：0111，1001，1100和1111。于是可得到如下一表：
|
23 = 8 |
22 = 4 |
21 = 2 |
20 = 1 |
|
|
大小为7的堆 |
0 |
1 |
1 |
1 |
|
大小为9的堆 |
1 |
0 |
0 |
1 |
|
大小为12的堆 |
1 |
1 |
0 |
0 |
|
大小为15的堆 |
1 |
1 |
1 |
1 |
由Nim取子游戏的平衡条件可知，此游戏是一个非平衡状态的取子游戏，因此，游戏人A在按获胜策略进行取子游戏下将一定能够取得最终的胜利。具体做法有多种，游戏人A可以从大小为12的堆中取走11枚硬币，使得游戏达到平衡（如下表），
|
23 = 8 |
22 = 4 |
21 = 2 |
20 = 1 |
|
|
大小为7的堆 |
0 |
1 |
1 |
1 |
|
大小为9的堆 |
1 |
0 |
0 |
1 |
|
大小为12的堆 |
0 |
0 |
0 |
1 |
|
大小为15的堆 |
1 |
1 |
1 |
1 |
证明各大网上有，在这就不讲述了。
最后贴下代码：
#include<cstdio>>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
int n,judge,item;
while(scanf("%d",&n)!=EOF)
{
scanf("%d",&judge);
for(int i=1;i<n;i++){
scanf("%d",&item);
judge^=item;
}
if(judge==0) printf("B\n");
else printf("A\n");
}
return 0;
}
第二篇：组合数学（第二抄）