CF1784F.Minimums or Medians
NOI/NOI+/CTSC
通过率:0%
时间限制:4.00s
内存限制:512MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Vika has a set of all consecutive positive integers from 1 to 2n, inclusive.
Exactly k times Vika will choose and perform one of the following two actions:
- take two smallest integers from her current set and remove them;
- take two median integers from her current set and remove them.
Recall that medians are the integers located exactly in the middle of the set if you write down its elements in increasing order. Note that Vika's set always has an even size, thus the pair of median integers is uniquely defined. For example, two median integers of the set 1,5,6,10,15,16,18,23 are 10 and 15.
How many different sets can Vika obtain in the end, after k actions? Print this number modulo 998244353. Two sets are considered different if some integer belongs to one of them but not to the other.
维卡拥有一组从 1 到 2n(含)的所有连续正整数。
维卡将恰好执行 k 次操作,每次选择并执行以下两种操作之一:
- 从当前集合中取出两个最小的整数,并将它们移除;
- 从当前集合中取出两个中位数整数,并将它们移除。
注意:若将集合中的元素按升序排列,则中位数即为恰好位于中间位置的两个数。由于维卡的集合大小始终为偶数,因此这一对中位数是唯一确定的。例如,集合 {1,5,6,10,15,16,18,23} 的两个中位数是 10 和 15。
在执行 k 次操作后,维卡最终可能得到多少种不同的集合?请输出该数目对 998244353 取模的结果。若某个整数属于其中一个集合但不属于另一个集合,则认为这两个集合不同。
输入格式
The only line contains two integers n and k (1≤k≤n≤106).
唯一的一行包含两个整数 n 和 k(1≤k≤n≤106)。
输出格式
Print a single integer — the number of sets Vika can obtain in the end, modulo 998244353.
输出一个整数——Vika 最终能够得到的集合数量,对 998244353 取模。
输入输出样例
输入#1
3 1
输出#1
2
输入#2
3 2
输出#2
3
输入#3
3 3
输出#3
1
输入#4
7 4
输出#4
11
输入#5
23 8
输出#5
88
输入#6
100 77
输出#6
825430474
说明/提示
In the first example, Vika's initial set is 1,2,3,4,5,6. She can remove the minimums from it to obtain 3,4,5,6, or she can remove the medians from it to obtain 1,2,5,6.
In the second example, Vika can obtain 1,6, 3,6, or 5,6. For instance, Vika can obtain 3,6 if she removes two smallest integers first (1,2,3,4,5,6→3,4,5,6), and then she removes two median integers (3,4,5,6→3,6).
In the third example, regardless of Vika's choices, she'll end up with an empty set.
在第一个例子中,维卡的初始集合为 {1,2,3,4,5,6}。她可以通过移除最小值得到 {3,4,5,6},也可以通过移除中位数得到 {1,2,5,6}。
在第二个例子中,维卡可以得到 {1,6}、{3,6} 或 {5,6}。例如,若她首先移除两个最小的整数({1,2,3,4,5,6}→{3,4,5,6}),再移除两个中位数({3,4,5,6}→{3,6}),即可得到 {3,6}。
在第三个例子中,无论维卡如何选择,最终都将得到空集。
输入解题思路,AI测评打分。不知道怎么写?