目录
Codeforces Round #654 (Div. 2)
E2. Asterism (Hard Version)
题意
给定 $n$ 个正整数，代表 $n$ 个敌人，每个敌人有 $a_i$ 颗糖，再给定一个素数 $p(p \le n)$。
定义游戏规则为一开始玩家拥有若干颗糖，每次玩家可以选取一个未挑战且手上糖果数不大于玩家的敌人，打败他获得一颗糖果。
定义 $f(x)$ 为玩家一开始拥有 $x$ 颗糖时可以战胜所有敌人的方案数。
要求输出所有满足 $p\nmid f(x)$ 的 $x$。
题解 $1$
设 $b_i$ 为糖果数不大于 $i$ 的敌人个数，$C_i(x)=b_{x+i}-i$。
有 $f(x)=\prod_{i=0}^{n-1} C_i(x)$。
易知 $C_{n-1}(x)\le 1$ 且 $C_i(x)-C_{i-1}(x)=b_{x+i}-1\ge -1$。
所以 $p\nmid f(x)\iff \forall i(0\le i\lt n \longrightarrow C_i\lt p)$。
由于 $C_i(x)\le C_i(x+1)$，所以答案为一段区间。
考虑 $x$ 的可能范围，记 $A=\max a_i$。若 $x\le A-n$，则 $f(x)= 0$，有 $p\mid f(x)$。若 $x\ge A$，则 $f(x)= n!$，有 $p\mid f(x)$。
所以将区间左端点初值设为 $A-n+1$，右端点初值设为 $A$，暴力枚举 $i=0\sim n-1$ 的情况，维护一下即可，时间复杂度 $O(n)$。
题解 $2$
$f(x)=\prod_{i=0}^{n-1} C_i(x)=\prod_{i=0}^{n-1} b_{x+i}-i=\prod_{i=x}^{x+n-1} b_{i}-i+x$。
所以 $p\nmid f(x)\iff$ 对所有 $x\le i\lt x+n$，有 $x$ 与 $i-b_{i}$ 不同余 $\iff$ $x-(A-n)$ 与 $i-(A-n)-b_{i}$ 不同余。
暴力枚举 $A-n\lt x\lt A$，考虑 $i-b_{i}$ 对于 $x$ 与 $x-1$ 的约束只用一项不同，所以可以用滑动窗口维护。
