A15741 | Minimums or Medians
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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 $998\,244\,353$ . Two sets are considered different if some integer belongs to one of them but not to the other.
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 $998\,244\,353$ . Two sets are considered different if some integer belongs to one of them but not to the other.
输入格式
The only line contains two integers $n$ and $k$ ( $1 \le k \le n \le 10^6$ ).
输出格式
Print a single integer — the number of sets Vika can obtain in the end, modulo $998\,244\,353$ .
输入输出样例
输入 #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\} \rightarrow \{3, 4, 5, 6\}$ ), and then she removes two median integers ( $\{3, 4, 5, 6\} \rightarrow \{3, 6\}$ ).
In the third example, regardless of Vika's choices, she'll end up with an empty set.
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\} \rightarrow \{3, 4, 5, 6\}$ ), and then she removes two median integers ( $\{3, 4, 5, 6\} \rightarrow \{3, 6\}$ ).
In the third example, regardless of Vika's choices, she'll end up with an empty set.
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?
提交通过
评测结果:Accepted