{"problem":{"name":"「CROI · R1」浣熊的溪石","description":{"content":"日升月落，春去秋来，梦枫溪石的高度千变万化。 爱思考的小浣熊 CleverRaccoon 想探寻这些溪石究竟能构成多少种不同的高度序列。 现有若干个长度为 $n$ 的非负整数列 $a$。 当 $n>1$ 时，$a_1,a_n$ 的取值为 $0\\sim m$，其它数 $a_i$ 的取值为 $0\\sim m-1$，其中 $2\\leq i \\leq n-1$。 当 $n=1$ 时，$a_1$ 的取","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":128000},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9554"},"statements":[{"statement_type":"Markdown","content":"日升月落，春去秋来，梦枫溪石的高度千变万化。\n爱思考的小浣熊 CleverRaccoon 想探寻这些溪石究竟能构成多少种不同的高度序列。\n\n现有若干个长度为 $n$ 的非负整数列 $a$。\n\n当 $n>1$ 时，$a_1,a_n$ 的取值为 $0\\sim m$，其它数 $a_i$ 的取值为 $0\\sim m-1$，其中 $2\\leq i \\leq n-1$。\n\n当 $n=1$ 时，$a_1$ 的取值为 $0\\sim m+1$。\n\n**定义**：当且仅当 $\\forall i\\in\\{1,2,\\dots ,n\\},a_i=b_i$ 或 $\\forall i\\in\\{1,2,\\dots ,n\\},a_i=b_{n-i+1}$ 时，数列 $a,b$ 相同。\n\n现给定 $n,m$，请求出最多有多少个**不同**的数列，答案对 $998244353$ 取模。\n\n## Input\n\n**本题包含多组测试数据。**\n\n第一行，输入一个正整数 $T$，表示数据组数。\n\n接下来 $T$ 行，每行输入以空格间隔的 $2$ 个正整数 $n,m$，意义见题目描述。\n\n## Output\n\n共 $T$ 行，对于每组数据，一行输出一个正整数，表示答案对 $998244353$ 取模的结果。\n\n[samples]\n\n## Background\n\n>回首往昔，碧空如洗，日暖风恬。\\\n溪石深浅有致地错落在明澈似玉的梦枫溪里。\\\n浣熊们水上跑酷的无限趣忆亦于此伊始……\n\n## Note\n\n#### 解释 #1\n\n当 $n=1,m=3$ 时，$a_i\\in\\{0,1,2,3,4\\}$，共有 $5$ 种不同的高度序列。\n\n当 $n=2,m=2$ 时，共有 $6$ 种不同的高度序列，详情如下：\n\n|序号|$a_1=$|$a_2=$|\n|:-:|:-:|:-:|\n|$1$|$0$|$0$|\n|$2$|$0$|$1$|\n|$3$|$0$|$2$|\n|$4$|$1$|$1$|\n|$5$|$1$|$2$|\n|$6$|$2$|$2$|\n\n#### 数据范围\n**本题采用 Subtask 捆绑测试。**\n\n|Subtask|$n\\leq$|$m\\leq$|$T\\leq$|特殊性质|Score|\n|:-:|:-:|:-:|:-:|:-:|:-:|\n|$0$|$10$|$10$|$10$|无特殊性质|$10$|\n|$1$|$10^3$|$1$|$10^3$|$m=1$|$5$|\n|$2$|$10^3$|$3$|$10$|$m=3$|$10$|\n|$3$|$10^3$|$10^3$|$1$|无特殊性质|$15$|\n|$4$|$10^6$|$10^3$|$100$|无特殊性质|$10$|\n|$5$|$10^6$|$10^6$|$10^6$|无特殊性质|$20$|\n|$6$|$10^9$|$10^9$|$10^6$| $n$ 为奇数|$10$|\n|$7$|$10^9$|$10^9$|$10^6$| $n$ 为偶数|$10$|\n|$8$|$10^{18}$|$10^9$|$10^6$|无特殊性质|$10$|\n\n对于 $100\\%$ 的数据，保证 $1\\leq n\\leq10^{18},1\\leq m\\leq10^9,1\\leq T\\leq10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9554","tags":["O2优化"],"sample_group":[["3\n1 3\n2 2\n6 3","5\n6\n666\n"]],"created_at":"2026-03-03 11:09:25"}}