Erdos-Ginzburg-Ziv Theorem
Erdos-Ginzburg-Ziv Theorem
对任意 $2n-1$ 个整数，可以从中选出 $n$ 个使得这 $n$ 个数的和是 $n$ 的倍数。
形式化的，对任意 $a_1,\dots,a_{2n-1}\in \mathbb Z$，存在两两不同的 $i_1,\dots,i_n$ 使得：
$$
a_{i_1}+\dots+ a_{i_n}\equiv 0\pmod n
$$
Solution. 取石子游戏
Description
$n$ 堆石子，第 $i$ 堆有 $a_i$ 个石子，颜色为 $c_i$。A 和 B 轮流行动，A 先手，每人有两种操作：
- 选择一堆石子并从中取出任意个石子。
- 选择一种颜色并从若干堆这种颜色的石子中取出不超过 $m$ 个石子。
不能不取。不能操作的人失败。
做题笔记 2023.2
CF808G Anthem of Berland
数据范围明示 dp。首先在模式串上跑 kmp，预处理失配指针，dp 时遇到问号就暴力枚举字符集中每个字母，复杂度为 $O(|\Sigma|\cdot|S|\cdot|T|)$，可以卡过。