五一省选真题分享
五一|省选真题分享五一|省选真题分享 P4071 - SDOI2016 - D2T1 - 排列计数 题目信息 难度:提高+/省选- 算法:数学递推、逆元 题目描述 求有多少种 $1$ 到 $n$ 的排列 $a$,满足序列恰好有 $m$ 个位置 $i$,使得 $a_i=i$. 答案对 $10^9+7$ 取模,多组询问,询问次数为 $T$. 测试点编号…
Luogu – P3509 – [POI2010]ZAB-Frog
数轴上有 $n$ 个点,坐标分别为 $p_1, p_2, \cdots, p_n$ 在这些点上按照某些规则跳。
规则是:每次向距当前点第 $k$ 小的点跳,如果有相同距离则向下标较小的跳;
求从每个点出发跳了 $m$ 次后在哪里.
$1\leq k < n\leq 10^6, 1\leq m\leq 10^{18}, 1\leq p_i\leq 10^{18}$.
Luogu – P5677 – [GZOI2017]配对统计
给定一个数列 $a_1, a_2, \cdots, a_n$.
定义在有序数对 $(x, y)$ 上的“好对”:对于 $a_x$,$y\in[1, x)\cup(x, n]$ 能使 $|a_x-a_y|$ 取最小值。
给定 $q\leq 3\times 10^5$ 组询问,每次询问一个区间 $[l, r]$ 中,有多少个好对。
求:每次询问的答案 $Ans_i$ 与询问编号 $i$ 的乘积的和,即:
$$ \sum_{i=1}^{m}Ans_i\times i $$