CF960G.Bandit Blues
省选/NOI-
通过率:0%
时间限制:3.50s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Japate, while traveling through the forest of Mala, saw N bags of gold lying in a row. Each bag has some distinct weight of gold between 1 to N. Japate can carry only one bag of gold with him, so he uses the following strategy to choose a bag.
Initially, he starts with an empty bag (zero weight). He considers the bags in some order. If the current bag has a higher weight than the bag in his hand, he picks the current bag.
Japate put the bags in some order. Japate realizes that he will pick A bags, if he starts picking bags from the front, and will pick B bags, if he starts picking bags from the back. By picking we mean replacing the bag in his hand with the current one.
Now he wonders how many permutations of bags are possible, in which he picks A bags from the front and B bags from back using the above strategy.
Since the answer can be very large, output it modulo 998244353.
Japate 在穿越玛拉森林时,看到一排整齐摆放的 N 只金袋。每只金袋所含黄金的重量互不相同,且均在 1 到 N 之间。Japate 只能随身携带一只金袋,因此他采用如下策略来挑选金袋:
初始时,他手中为空袋(即重量为 0)。他按某种顺序依次考虑这些金袋;若当前金袋的重量大于他手中金袋的重量,则他便用当前金袋替换手中金袋。
Japate 将这 N 只金袋以某种顺序排列。他发现:若从排列的前端开始依次考虑金袋,他总共会进行 A 次替换;而若从排列的后端开始依次考虑金袋(即反向遍历),他总共会进行 B 次替换。(此处“替换”指用当前金袋替换手中金袋。)
现在他想知道:满足上述条件(即从前端开始替换 A 次、从后端开始替换 B 次)的金袋排列(即 1 到 N 的排列)共有多少种?
由于答案可能非常大,请输出其对 998244353 取模的结果。
输入格式
The only line of input contains three space separated integers N (1 ≤ N ≤ 105), A and B (0 ≤ A, B ≤ N).
输入仅有一行,包含三个以空格分隔的整数 N(1 ≤ N ≤ 105)、A 和 B(0 ≤ A, B ≤ N)。
输出格式
Output a single integer — the number of valid permutations modulo 998244353.
输出一个整数——模 998244353 意义下的有效排列数目。
输入输出样例
输入#1
1 1 1
输出#1
1
输入#2
2 1 1
输出#2
0
输入#3
2 2 1
输出#3
1
输入#4
5 2 2
输出#4
22
说明/提示
In sample case 1, the only possible permutation is [1]
In sample cases 2 and 3, only two permutations of size 2 are possible:{[1, 2], [2, 1]}. The values of a and b for first permutation is 2 and 1, and for the second permutation these values are 1 and 2.
In sample case 4, out of 120 permutations of [1, 2, 3, 4, 5] possible, only 22 satisfy the given constraints of a and b.
在样例 1 中,唯一可能的排列是 [1]
在样例 2 和样例 3 中,仅存在两种长度为 2 的排列:{[1, 2], [2, 1]}。对于第一个排列,a 和 b 的值分别为 2 和 1;对于第二个排列,a 和 b 的值分别为 1 和 2。
在样例 4 中,在 [1, 2, 3, 4, 5] 的全部 120 种排列中,仅有 22 种满足给定的 a 和 b 约束条件。
输入解题思路,AI测评打分。不知道怎么写?