Problems for Codeforces

题意翻译

#### 题目描述 XYMXYM 与 CQXYM 将为 Codeforces 准备 $n$ 个题目。第 $i$ 个题目的难度为整数 $a_i$ 且 $a_i\geq 0$。所有题目的难度必须满足 $a_i+a_{i+1}\lt m\,\space(1\leq i\lt n)$ 且 $a_1+a_n\lt m$，其中 $m$ 为一个固定整数。XYMXYM 想知道题目难度有多少种可能的方案，结果对 $998244353$ 取模。 两种题目难度的方案 $a$ 和 $b$ 是不同的当且仅当存在一个整数 $i,\space (1\leq i\leq n)$ 满足 $a_i\neq b_i$。 #### 输入格式 一行包含两个整数 $n$ 和 $m$ $(2\leq n\leq 50\,000,1\leq m\leq 10^9)$。 #### 输出格式 输出一个整数为方案数，对 $998244353$ 取模。 #### 说明/提示 在第一个样例中，合法的方案为 $[0,0,0],[0,0,1],[0,1,0],[1,0,0]$，而 $[1,0,1]$ 不合法因为 $a_1+a_n\geq m$。

题目描述

XYMXYM and CQXYM will prepare $ n $ problems for Codeforces. The difficulty of the problem $ i $ will be an integer $ a_i $ , where $ a_i \geq 0 $ . The difficulty of the problems must satisfy $ a_i+a_{i+1}<m $ ( $ 1 \leq i < n $ ), and $ a_1+a_n<m $ , where $ m $ is a fixed integer. XYMXYM wants to know how many plans of the difficulty of the problems there are modulo $ 998\,244\,353 $ . Two plans of difficulty $ a $ and $ b $ are different only if there is an integer $ i $ ( $ 1 \leq i \leq n $ ) satisfying $ a_i \neq b_i $ .

输入输出格式

输入格式

A single line contains two integers $ n $ and $ m $ ( $ 2 \leq n \leq 50\,000 $ , $ 1 \leq m \leq 10^9 $ ).

输出格式

Print a single integer — the number of different plans.

输入输出样例

输入样例 #1

3 2

输出样例 #1

4

输入样例 #2

5 9

输出样例 #2

8105

输入样例 #3

21038 3942834

输出样例 #3

338529212

说明

In the first test case, the valid $ a $ are: $ [0,0,0] $ , $ [0,0,1] $ , $ [0,1,0] $ , $ [1,0,0] $ . $ [1,0,1] $ is invalid since $ a_1+a_n \geq m $ .