[BZOJ3771]Triple

生成函数 , FFT , NTT

不同情况的生成函数

我们先设 $𝑎 (𝑥)$ 为丢失一把斧头的生成函数， $𝑏 (𝑥)$ 为丢失两把一样的斧头的生成函数， $𝑐 (𝑥)$ 为丢失三把一样的斧头的生成函数

对于样例来说：

𝑎 (𝑥) = 𝑥 4 + 𝑥 5 + 𝑥 6 + 𝑥 7 𝑏 (𝑥) = 𝑥 8 + 𝑥 10 + 𝑥 12 + 𝑥 14 𝑐 (𝑥) = 𝑥 12 + 𝑥 15 + 𝑥 18 + 𝑥 21

再设 $𝐴 (𝑥)$ 为丢失一把斧头的生成函数， $𝐵 (𝑥)$ 为丢失两把不同的斧头的生成函数， $𝐶 (𝑥)$ 为丢失三把不同的斧头的生成函数

对于样例来说：

𝐴 (𝑥) = 𝑎 (𝑥) 𝐵 (𝑥) = 𝑎 2 (𝑥) - 𝑏 (𝑥) 𝐶 (𝑥) = 𝑎 3 (𝑥) - 3 𝑎 (𝑥) 𝑏 (𝑥) + 2 𝑐 (𝑥)

解释一下 $𝐶 (𝑥)$ ，首先随意的选择三个斧头（可以相同），然后减去选出两把相同的斧头和另一把斧头（也可以相同），但是三个相同的被减了三次，所以要加 $2$

由于数据范围较大，需要用 FFT 或 NTT 优化

solution-code2593

每种水的生成函数

第 1 种： $1 + 𝑥 + 𝑥 2 + \dots = 1 1 - 𝑥$

第 2 种： $1 + 𝑥 = 1 - 𝑥 2 1 - 𝑥$

第 3 种： $1 + 𝑥 + 𝑥 2 + 𝑥 3 + 𝑥 4 = 1 - 𝑥 5 1 - 𝑥$

第 4 种： $1 + 𝑥 5 + 𝑥 10 + \dots = 1 1 - 𝑥 5$

第 5 种： $1 + 𝑥 2 + 𝑥 4 + \dots = 1 1 - 𝑥 2$

乘在一起得到： $1 (1 - 𝑥) 3 = (1 - 𝑥) - 3$

带入广义二项式定理得： $𝑓 (𝑥) = \sum \infty 𝑖 = 0 𝐶 𝑖 𝑖 + 2 \cdot 𝑥 𝑖$

当 $𝑖 = 𝑛$ 时第 $𝑛$ 项为 $𝑥 \cdot 𝐶 𝑛 𝑛 + 2 \cdot 𝑥 𝑛 = 𝐶 2 𝑛 + 2 \cdot 𝑥 𝑛$

所以答案就为 $a n s = (𝑛 + 1) (𝑛 + 2) 2$

solution-code4763

每种食物的生成函数

汉堡: $1 + 𝑥 2 + 𝑥 4 + \dots = 1 1 - 𝑥 2$

可乐: $1 + 𝑥 = 1 - 𝑥 2 1 - 𝑥$

鸡腿: $1 + 𝑥 + 𝑥 2 = 1 - 𝑥 3 1 - 𝑥$

蜜桃多: $𝑥 + 𝑥 3 + 𝑥 5 + \dots = 𝑥 1 - 𝑥 2$

鸡块: $1 + 𝑥 4 + 𝑥 8 + \dots = 1 1 - 𝑥 4$

包子: $1 + 𝑥 + 𝑥 2 + 𝑥 3 = 1 - 𝑥 4 1 - 𝑥$

土豆片炒肉: $1 + 𝑥 = 1 - 𝑥 2 1 - 𝑥$

面包: $1 + 𝑥 3 + 𝑥 6 + \dots = 1 1 - 𝑥 3$

乘在一起得到: $𝑓 (𝑥) = 𝑥 (1 - 𝑥) 4 = 𝑥 \cdot (1 - 𝑥) - 4$

带入广义二项式定理得 $𝑓 (𝑥) = 𝑥 \cdot \sum \infty 𝑖 = 0 𝐶 𝑖 𝑖 + 3 \cdot 𝑥 𝑖$

当 $𝑖 = 𝑛 - 1$ 时第 $𝑛 - 1$ 项为 $𝑥 \cdot 𝐶 𝑛 𝑛 + 2 \cdot 𝑥 𝑛 = 𝐶 3 𝑛 + 2 \cdot 𝑥 𝑛$

所以答案就为 $a n s = 𝑛 (𝑛 + 1) (𝑛 + 2) 6$

[BZOJ3759] Hungergame

线性基 , Nim

转载自joyouth

首先我们不难看出如果存在一个异或和为 $0$ 的子集，那么先手必胜，否则先手必败

证明如下：

首先如果至少存在一个异或和为 $0$ 的子集，那么一定存在一个异或和为 $0$ 的子集使得选取之后剩下的数的任意子集异或和不为 $0$
假设我们已经选取了一个异或和为 $0$ 的子集，无论后手怎么做，我们总是有办法使得当前选取的子集异或和为 $0$ ，因为后手无论是拿石子还是取石子之后，当前子集异或和不等于 $0$ ，根据 Nim 游戏可知，此时先手一定有方案使得异或和为 $0$

至此，我们证明了如果至少存在一个异或和为 $0$ 的子集，先手必胜

那么题目就转化为求是否存在一个子集异或和为 $0$ ，用线性基即可

生成函数

注意：