**序：**博弈是信息学和数学试题中常会出现的一种类型，算法灵活多变是其最大特点，而其中有一类试题更是完全无法用常见的博弈树来进行解答。 寻找必败态即为针对此类试题给出一种解题思路。

给６个矩形的长和宽（或者宽和长），问这六个矩形能否组成一个长方体．

思路比较简单，不过需要注意的地方有点多．

首先由于长和宽的顺序为止，所以要处理一下（一开始只处理了后来读入的五组，没有处理单独读入的第一组，差评）

比赛的时候没过．还以为是树状数组写残了． 但实际上是有自己不知道的东西． 这种博弈叫　nim游戏 所以这是一个二维的nim游戏． **nim游戏的性质是xor 和为0必败，否则必胜． xor和也有前缀和性质，所以可以用树状数组维护．

假设有n堆石子，每堆石子的个数分别如下

a1, a2, a3, ... an

定义nim-sum为a1^a2^a3...an

可以证明

1. 若a1^a2^a3...an != 0

则经过一次合法的移动之后必定可变成

果然dp還是弱項啊啊啊啊．． 不過比最開始的完全無從下手強了不少應該．．．

至少dp狀態表示相對了．．．．轉移方程沒想出來嗚嗚嗚

官方題解：设d(i, j)d(i,j)表示前ii个数，模pp为jj的方案数，则容易得到d(0, 0)=1, d(i, j)=d(i-1, j)+sum_{j=0}^{p-1} d(i-1, (j-a[i]) mod p)d(0,0)=1,d(i,j)=d(i−1,j)+∑​j=0​p−1​​d(i−1,(j−a[i]) mod p)，很多人没1a是因为没注意|a_i| le 10^9∣a​i​​∣≤10​9​​

贪心．．尽量把一样的材料放在一起．．． 然后写蠢了．．妈蛋．．． 详情见代码

/*************************************************************************
	> File Name: code/bc/#56/1001.cpp
	> Author: 111qqz
	> Email: rkz2013@126.com 
	> Created Time: 2015年09月19日 星期六 18时55分49 …

x的二进制表示中1的个数即为答案．

原因是，每天晚上糖果数量翻倍，相当于左移１位,这时候二进制表示中1的数量不变

也就是说，二进制表示中的所有的1，一定都是添加进去的

初识分快.

引一段题解：

Let's split rectangle 106 × 106 by vertical lines into 1000 rectangles 103 × 106. Let's number them from left to right. We're going to pass through points rectangle by rectangle. Inside the rectangle we're going to pass the points in increasing order of y-coordinate if the number of rectangle is even and …

因为每一个正整数可以唯一分解质因数...

要看能猜多少次，只要知道不大于n的质因子数有多少个即可（相同的算多

由于n才是１０００．所以素数表随便搞就好....不用筛也行...

背包还是理解的不够透彻．．

因为每次都是用那个一维形式的．

这道题的做法类似01背包.

此外还可以有一个优化...

当n>m的时候．．．根绝抽屉原理．．一定为yes..