题解：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)。