题目背景
原 维护队列 参见 P1903
题目描述
某一天 WJMZBMR 在打 osu，但是他太弱了，有些地方完全靠运气:(。
我们来简化一下这个游戏的规则
P2473 [SCOI2008] 奖励关
题目描述
你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出 $k$ 次宝物，每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。
宝物一共有 $n$ 种，系统每次抛出这 $n$ 种宝物的概率都相同且相互独立。也就是说，即使前 $(k-1)$ 次系统都抛出宝物 $1$（这种情况是有可能出现的，尽管概率非常小），第 $k$ 次抛出各个宝物的概率依然均为 $\frac{1}{n}$。
获取第 $i$ 种宝物将得到 $p_i$ 分，但并不是每种宝物都是可以随意获取的。第 $i$ 种宝物有一个前提宝物集合 $s_i$。只有当 $s_i$ 中所有宝物都至少吃过一次，才能吃第 $i$ 种宝物（如果系统抛出了一个目前不能吃的宝物，相当于白白的损失了一次机会）。注意，$p_i$ 可以是负数，但如果它是很多高分宝物的前提，损失短期利益而吃掉这个负分宝物将获得更大的长期利益。
假设你采取最优策略，平均情况你一共能在奖励关得到多少分值？
P4931 [MtOI2018] 情侣？给我烧了！（加强版）
P6791 [SNOI2020] 取石子
题目描述
甲乙两个人玩取石子游戏。他们面前有一堆共 $n$ 个石子，然后由甲先手，两人轮流从中取走石子：甲第一次取走的个数不能超过 $k$，接下来每个人取走的个数不能超过上一个人刚刚取走个数的 $2$ 倍。每人每次必须至少取一个石子。取走最后一个石子的人失败，另一方获胜。现在已知 $k$，请你求出在 $1$ 到 $N$ 中有多少整数 $n$ 使得甲在 $n$ 颗石子的游戏中有必胜策略。
输入格式
多组数据。
第一行一个正整数 $T$ 表示数据组数。
P5860 「SWTR-3」Counting Trees
题目背景
一个风和日丽的早晨，小 $\mathrm{S}$ 带着他的好朋友小 $\mathrm{A}$ 在小树林里面数树。
看着满树林的树，小 $\mathrm{S}$ 灵感一闪，想到了一道题目。
$$ \mathrm{Suddenly,\ Little\ S\ thought\ of\ a\ supercalifragilisticexpialidocious\ problem.} \ \mathrm{He\ wanted\ Little\ A\ to\ answer\ it.} $$
题目描述
P7364 有标号二分图计数
P3702 [SDOI2017] 序列计数
题目描述
Alice 想要得到一个长度为 $n$ 的序列，序列中的数都是不超过 $m$ 的正整数，而且这 $n$ 个数的和是 $p$ 的倍数。
Alice 还希望，这 $n$ 个数中，至少有一个数是质数。
Alice 想知道，有多少个序列满足她的要求。
输入格式
P3179 [HAOI2015] 数组游戏
$$ \def\xor{\text{ xor }} \def\mex{\mathrm{mex}} \def\SG{\mathrm{SG}} $$
题目描述
有一个长度为 $n$ 的数组，甲乙两人在上面进行这样一个游戏：首先，数组上有一些格子是白的，有一些是黑的。然后两人轮流进行操作。
每次操作选择一个白色的格子，假设它的下标为 $x$。接着，选择一个大小在 $1\ldots \lfloor \dfrac{n}{x} \rfloor$ 之间的整数 $k$，然后将下标为 $x,2\times x,\ldots ,k\times x$ 的格子都进行颜色翻转。不能操作的人输。
现在甲（先手）有一些询问。每次他会给你一个数组的初始状态，你要求出对于这种初始状态他是否有必胜策略。
FFT 和生成函数
多项式乘法
问题背景
给定两个多项式 $A(x)$ 和 $B(x)$：
$$ A(x) = a_0 + a_1x + a_2x^2 + \dots + a_nx^n \ B(x) = b_0 + b_1x + b_2x^2 + \dots + b_mx^m $$
我们需要计算它们的乘积 $C(x) = A(x) \cdot B(x)$。
P11617 [PumpkinOI Round 1] 递推
题目背景
一个简单的问题，什么是递推？
题目描述
定义一个数列 $\set{a_0 \dots a_{n - 1} }$ 的递推式为满足下式的序列 $\set{r_0\dots r_m}$：
$$ \sum_{j = 0} ^ m r_j a_{i - j} = 0, \forall i \ge m $$