题解：CF1371E2 Asterism (Hard Version)

记 $M=\max{a_i}$，那么满足条件的 $x$ 一定位于 $[M−n,M]$ 之间，这是因为在这个区间之外的 $f(x)$ 只可能为 $0$ 或 $n!$。

接下来计算 $f(x)$。

注意到，第 $i$ 次可以打的敌人第 $i+1$ 次也可以打，那么记 $\le i$ 个糖果的敌人数量为 $t_i$，第 $j$ 次能打的敌人的数量恰好为 $t_{x+j−1}−j+1=x−(x+j−1−t_{x+j−1})$。

总共的方案数就是这些数量乘起来，所以判断是否能被 $p$ 整除可以通过对每个数量判断。 

记 $g_i=i−t_i$，那么 $f(x)=\prod_{i=x}^{x+n−1}(x−g_i)$，若 $x$ 与某个 $g_i$ 在模 $p$ 意义下同余，那么 $p\mid f(x)$。

那么我们可以开一个桶记录在区间 $[x,x+n−1]$ 中 $g_i \bmod p$ 的值。从小往大枚举 $x$，并且更新桶即可。

时间复杂度 $O(n)$。