每种水的生成函数

第 1 种：$1+x+x^2+\cdots =\frac{1}{1-x}$

第 2 种：$1+x=\frac{1-x^2}{1-x}$

第 3 种：$1+x+x^2+x^3+x^4=\frac{1-x^5}{1-x}$

第 4 种：$1+x^5+x^{10}+\cdots =\frac{1}{1-x^5}$

第 5 种：$1+x^2+x^4+\cdots =\frac{1}{1-x^2}$

乘在一起得到：$\frac{1}{(1-x{)}^3}=(1-x{)}^{-3}$

带入广义二项式定理得：$f(x)=\sum _{i=0}^{\mathrm{\infty }}{C}_{i+2}^i\cdot x^i$

当$i=n$时第$n$项为$x\cdot C_{n+2}^n\cdot x^n=C_{n+2}^2\cdot x^n$

所以答案就为$\text{ans}=\frac{(n+1)(n+2)}{2}$

每种食物的生成函数

汉堡:$1+x^2+x^4+\cdots =\frac{1}{1-x^2}$

可乐:$1+x=\frac{1-x^2}{1-x}$

鸡腿:$1+x+x^2=\frac{1-x^3}{1-x}$

蜜桃多:$x+x^3+x^5+\cdots =\frac{x}{1-x^2}$

鸡块:$1+x^4+x^8+\cdots =\frac{1}{1-x^4}$

包子:$1+x+x^2+x^3=\frac{1-x^4}{1-x}$

土豆片炒肉:$1+x=\frac{1-x^2}{1-x}$

面包:$1+x^3+x^6+\cdots =\frac{1}{1-x^3}$

乘在一起得到:$f(x)=\frac{x}{(1-x{)}^4}=x\cdot (1-x{)}^{-4}$

带入广义二项式定理得$f(x)=x\cdot \sum _{i=0}^{\mathrm{\infty }}{C}_{i+3}^i\cdot x^i$

当$i=n-1$时第$n-1$项为$x\cdot C_{n+2}^n\cdot x^n=C_{n+2}^3\cdot x^n$

所以答案就为$\text{ans}=\frac{n(n+1)(n+2)}{6}$

转载自joyouth

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

证明如下：

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

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

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

注意：