BZOJ 3105中，如何运用拟阵解决新Nim游戏问题？

本文共计1740个文字，预计阅读时间需要7分钟。

首先，从网上下载一篇拟阵的简介：

拟阵是满足下列条件的序对（S，I）的一个满足条件集合：

1.S是一个有穷集合；

2.I是S的一类具有遗传性质的非空子集族；

遗传性质定义为：若B∈I且A∈B，则A∈I。

简单改写如下：

拟阵简介：拟阵是一个包含有穷集合S和具有遗传性质的非空子集族I的序对（S，I）。其中，遗传性质是指：如果B属于I，且A属于B，那么A也属于I。

首先先从网上转载一份‘拟阵’的简介：

拟阵

拟阵是满足下列条件的一个序对M=(S,I)；

1）S是一个有穷的集合。

2）I是S的一类具有遗传性质的非空子集族。遗传性质定义为：如果B∈I且A⊂B，那么A∈I。即若B∈I，则B是S的独立子集（独立子集的定义），且B的任意子集也都是S的独立子集。空集必为I的成员。注意，I是集合的集合。

3）I满足交换性质。交换性质定义为，若A∈I，B∈I且|A|<|B|，则存在某一元素x∈B-A，使得A∪{x}属于I。（这条性质给了我们已知集合B，构造集合A的方法。而性质2暗示了我们已知集合B，找出其子集的性质的办法）

下面是一个拟阵的例子：

无向图G=(V,E)的拟阵，定义为M[G]=(S[G],I[G])。

*集合S[G]定义为E，即G的边集。

*如果A是E的子集，而且A是无回路的，则A属于IG。亦即，一组边A是独立的当且仅当子图G[A]=（V，A）构成了一个森林。

下面证明M[G]是一个拟阵。

1）显然S[G]=E是一个有穷集合。

2）I[G]是遗传的。对于任意的B∈I[G]，A⊂B，边集A都∈I[G]，原因是从无环的一组边中去掉一些边并不会产生出回路。