I am bike.
ABC465G
简要题意
给你一个整数 $N,M,C,K$ 和一个长度为 $N$ 的整数序列 $A=(A _ 1,A _ 2,\ldots,A _ N)$ 。
给你 $Q$ 个查询，你应该按顺序处理这些查询。在 $q$ -th $(1\le q\le Q)$ 查询中得到了整数 $i _ q,X _ q$ ，在将 $A _ {i _ q}$ 更改为 $X _ q$ 之后，你应该解决下面的问题。
求 $\displaystyle \sum _ {k=0}^{K-1} \mathop{\mathrm{mex}}\limits _ {1 \le i \le N} \lbrace (Ck+A _ i)\bmod M\rbrace$ 的值。这里的 $\displaystyle \mathop{\mathrm{mex}}\limits _ {1 \le i \le N} B _ i$ 表示整数序列 $B=(B _ 1,B _ 2,\ldots,B _ N)$ 中不包含在 $B$ 中的最小非负整数。
- $1\le N\le 2\times 10^5$
- $0\le C < M \le 10^9$
- $1\le K\le 10^9$
- $0\le A_i < M$
- $1\le Q\le 2\times 10^5$
- $1\le i_q \le N$
- $0\le X_q < M$
题解
尝试用抽象思维解读题目这个集合 $S_k=\{(k\times C+a_i)\bmod M|1\leq i \leq n\}$。不妨考虑有一个首尾相连的 $M$ 个点的环，将编号等于某个 $a_i$ 的所有位置打上标记，接着从编号为 $-kC\bmod M$ 的位置开始，$\text{mex}(S_k)$ 即为从这个位置开始走几步能走到没打上标记的位置。
下文部分表述省略对 $M$ 取模。
接着考虑标记一个位置/取消标记一个位置会对答案产生什么影响，假设需要标记 $x$，那么求出从 $x-1$ 开始往左的极长连续标记段和从 $x+1$ 开始往右的极长连续标记段，设最左和最右分别为 $L,R$（当标记 $x$ 后所有位置都被标记时，作为特殊情况特判处理），那么答案会增加 $(R-x+1)\times \text{tot}_{[L,x-1]}$ 其中 $tot_{[l,r]}$ 是 $-kC\bmod M$ 落在区间 $[l,r]$ 内的次数。取消标记则是逆过程。
关于 $L,R$ 的求值与连续段的维护可以使用 std::set 不过多赘述，最关键的问题是 $\text{tot}_{[l,r]}$ 的求法。
不妨令 $0\leq l\leq r< M $，设 $g=\text{gcd}(C,M),c=\frac{C}{g},m=\frac{M}{g}$，那么 $s_k=-kC\bmod M$ 只可能落在 $g$ 的倍数上。将 $l,r$ 压缩至模 $m$ 的完全剩余系中，即令 $l'=\lceil \frac{l}{m}\rceil,r'=\lfloor \frac{r}{m}\rfloor$。问题变成了，从 $s_0=0$ 开始，每次移动 $m-c$ 格，落在 $[l',r']$ 中的次数。这个问题可以用类欧几里得算法解决，具体的，利用 $[(a\times x+b)\bmod c < y] = \lfloor\frac{a\times x+b}{c}\rfloor-\lfloor\frac{a\times x+b-y}{c}\rfloor$ 即可。
总时间复杂度 $O((n+q) \times (\log {n}+\log {10^9}))$。
SEQ2
简要题意
一个由整数 $[1, N]$ 构成的子集被称为好子集，当且仅当存在某个整数 $X$，使得 $X, X + 1, X + 2, \ldots, X + K - 1$ 中的每一个都属于该子集。
例如，当 $K = 3$ 时，$\{1, 2, 3, 5, 6\}$ 是一个好子集，但当 $K = 4$ 时则不是。
对于整数 $[1, N]$ 的一个排列 $P$，定义 $f(P)$ 为使集合 $P[1, i]$ 成为好子集的最短前缀的长度（记该长度为 $i$）。
例如，对于 $K = 3$，以及 $P = [1, 2, 5, 6, 3, 4]$，可以证明 $f(P) = 5$。
求所有 $N!$ 个可能的排列的 $f(P)$ 之和。由于答案可能很大，请输出结果对 $998244353$ 取模后的值。
- $1 \le T \le 1000$
- $2 \le K \le N \le 2 \cdot 10^5$
- 所有测试数据中 $N$ 的总和不超过 $2 \cdot 10^5$。
题解
答案等于 $n!+\sum_{i=1}^{n} f_i$ 其中 $f_i$ 表示前 $i$ 个数构成的集合中不存在长度为 $K$ 的编号连续段的方案数。
令 $p_0=0 < p_1 < p_2 < p_3 < ... < p_{N-i} < N+1=p_{N-i+1}$ 为所有不在前缀 $i$ 内的元素，则有限制 $p_{j+1}-p_j\leq K$ 对所有 $j$ 满足。枚举 $j$ 表示钦定 $j$ 个 $p$ 的间隙大于 $K$，则 $f_i=\sum_{j=0}^{\min(N-i+1,\lfloor \frac{N}{K}\rfloor)} (-1)^j \binom{N-i+1}{j} \binom{N-jK}{N-i}i!(N-i)!$。
$Ans=\sum_{i=1}f_i=\sum_{j=0}^{\lfloor \frac{N}{K}\rfloor} \sum_i (-1)^j\binom{i+1}{j}\binom{N-jk}{i}i!(N-i)!$。
对于固定的 $j$，有
$\sum_i (-1)^j\binom{i+1}{j}\binom{N-jk}{i}i!(N-i)!=\sum_i (-1)^j\binom{i+1}{j}\frac{(N-jk)!i!(N-i)!}{(N-jk-i)!i!}=$
$\sum_i (-1)^j\binom{i+1}{j}\frac{(N-jk)!(N-i)!(jk)!}{(N-jk-i)!(jk)!}=(-1)^j (N-jk)!(jk)! \sum_i \binom{N-i}{jk}\binom{i+1}{j}$，右侧是范德蒙德卷积直接化成 $\binom{N+1}{jk+j}$。
时间复杂度 $O(N)$。
