luogu#P8962. 「WHOI-4」yadiw. Slua, gassp, lhtubs.
「WHOI-4」yadiw. Slua, gassp, lhtubs.
题目背景
If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
题目描述
小 F 有一个奇妙的数组 , 中没有重复的元素,长度为 ,他使用std::sort
将他排序了,认为它是有序的,所以他正在使用这样的方法进行二分查找。显然,能否查到只和数列的离散化结果有关,所以你可以直接把 看作 的一个排列。
int search(int key) {
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] < key)
l = mid + 1;
else if (a[mid] == key)
return mid;
else
r = mid - 1;
}
return -1;
}
不幸的是,小 W 为了让他戒掉万能头,在bits/stdc++.h
中写了#define sort random_shuffle
,这意味着 实际是一个随机的排列。
现在,对于所有在 到 范围内的 ,以及所有在 到 范围内的 ,在 数列的所有排列中,有几个可以正确地找到第 小的元素 (即返回值非 )?由于答案可能过大,请输出它对给定模数 取模的结果。
输入格式
一行两个正整数 。
输出格式
行,第 行 个正整数,代表在 个元素中找 能找到的方案数。
998244353 5
1
1 2
4 4 4
12 12 14 18
48 54 60 66 72
提示
数据范围
本题采用 Subtask 评测。
- Subtask 1( pts):,;
- Subtask 2( pts):, 且为素数;
- Subtask 3( pts):, 且为素数;
- Subtask 4( pts):。
对于所有数据,,。