E Roaming
题面
有 $n$ 个房间 , 开始时每个房间有 1 个人 . 人们可以在各个房间中移动 ( 不能原地移动 ) . 所有人一共移动了 $k$ 次 .
求最后每个房间的人数排列有多少种情况 .
解题思路
明显的 , 数学题 . 当所有人移动完后 , 人数为 0 的房间最多有 $\min(n - 1 , k)$ 间 . 因此可以枚举移动完后空房子的数量 . 设空房间的数量为 $i$ , 则有 $n - i$ 个非空房间放人 . 在 $n - 1$ 个空中插入 $n - i - 1$ 个板 . 对于每一个 $i$ , 有 :
$$C_{n}^{i} \times C_{n - 1}^{n - i - 1}$$
累加即可 . 另外 , 数据较大 , 需要逆元 .
F Modularness
题面
有一个长度为 $k$ 的序列 , $d_0$ ,$d_1$ , … , $d_{k - 1}$.
有 $Q$ 次询问 , 每次询问给出三个数 . 同时定义长度为 $n$ 的序列 $a_0 , a_1 , \ldots ,a_{n - 1}$ . 其中 :
$$\begin{aligned} a_j = \begin{cases} x_i & ( j = 0 ) \newline a_{j - 1} + d_{(j - 1)\ \textrm{mod}\ k} & ( 0 < j \leq n - 1 ) \end{cases}\end{aligned}$$
对于每组询问 , 求有多少个 $j$ 满足 $0 \le j < n - 1$ 且 $(a_j \bmod\ m) < (a_{j+1} \bmod\ m)$ .
解题思路
正难则反 , 统计 $a_i \equiv a_{i+1}\ (\bmod\ m)$ 和 $(a_i \bmod\ m) > (a_{i+1} \bmod m)$ 两种情况的数量 .
先进行预处理 : 将所有 $d$ 对 $m$ 取模 , 对结果无影响 .
当 $d_{i \bmod k} = 0$ 时满足第一个条件 .
$(a_i \bmod\ m) > (a_{i+1} \bmod m)$ , 因为已经将所有的 $d$ 取模了 , 相当于我们现在进行的是 $m$ 进制运算 .
一次进位只可能使前一位的值恰好增加 1 , 因此我们只需要统计发生了多少次进位即可 .