{"problem":{"name":"「KDOI-02」一个仇的复","description":{"content":"外星人的空间站是一个环形结构。不过，由于环的两段不连通，因此可以将其近似为 $2\\times n$ 的平面网格。目前，地方飞船有 $n$ 种不同规格的射线武器，作用范围是 $1\\times x$（$x$ 为正整数）的长方形。并且，武器可以往顺时针或逆时针方向旋转 $90^\\circ$。射线十分强力，只需一发便可与作用范围平面内的所有物体相湮灭。不过，只要宇宙射线的一部分作用范围落到目标外，便会一直","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8594"},"statements":[{"statement_type":"Markdown","content":"外星人的空间站是一个环形结构。不过，由于环的两段不连通，因此可以将其近似为 $2\\times n$ 的平面网格。目前，地方飞船有 $n$ 种不同规格的射线武器，作用范围是 $1\\times x$（$x$ 为正整数）的长方形。并且，武器可以往顺时针或逆时针方向旋转 $90^\\circ$。射线十分强力，只需一发便可与作用范围平面内的所有物体相湮灭。不过，只要宇宙射线的一部分作用范围落到目标外，便会一直延续到宇宙尽头，贪婪地吞噬沿途的一切。指挥官当然不想危害到无辜文明，他想知道，在这 $n$ 中武器中选出 $k$ 种，共有多少种不同的摧毁飞行器的方式。\n\n**【形式化题意】**\n\n你有 $1\\times x$（$x$ 为任意正整数）的矩形各无穷多个和一个 $2\\times n$ 的网格，请求出恰好选择其中 $k$ 个矩形（可以选择相同的矩形）**不重不漏**地铺满整个网格的方案数。矩形可以旋转。\n\n## Input\n\n从标准输入中读入数据。\n\n输入共包含一行两个正整数 $n,k$。\n\n## Output\n\n输出到标准输出。\n\n输出一行一个正整数，表示方案数，答案对 $998244353$ 取模。\n\n[samples]\n\n## Background\n\n**本题由于 OI 赛制，关闭 subtask，可能会放部分错解高分，赛后将开启 subtask。**\n\n「听说那件事了吗？愿他们安息。」  \n「诶？你看，前面那座环形建筑是什么？」  \n「等我对比一下……啊哈！这就是他们的老巢！」  \n「捣毁了它，为牺牲的同志们报仇！！！」  \n死亡的宇宙射线指向了脆弱的文明，正准备发出它震耳欲聋的怒吼。\n\n## Note\n\n****\n**【样例解释】**\n+ **样例 1 解释：**  \n共有如下图所示的 $8$ 种方案。  \n![](https://cdn.luogu.com.cn/upload/image_hosting/iko97ksh.png)\n\n***\n**【数据范围】**\n\n对于 $100\\%$ 的数据，$1\\le n\\le 2\\times 10^7$，$1\\le k\\le 5000$。\n\n| 测试点编号 | 分值 | $n$ | $k$ |\n| :----------: | :----------: | :----------: | :----------: |\n|$1\\sim 5$| $2$ | $\\leq5$ | $\\leq10$ |\n|$6\\sim 10$| $2$ | $\\leq1000$ | $=2n$ |\n|$11\\sim 15$| $2$ | $\\leq10^6$ | $\\leq3$ |\n|$16\\sim 20$| $4$ | $\\leq1000$ | $\\leq2n$ |\n|$21\\sim 25$| $4$ | $\\leq2\\times10^7$ | $\\leq100$ |\n|$26\\sim 30$| $4$ | $\\leq10^6$ | $\\leq5000$ |\n|$31\\sim 40$| $1$ | $\\leq2\\times10^7$ | $\\leq5000$ |\n\n注意：分值一列指的是单个测试点分值。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8594","tags":["数学","2022","洛谷原创","O2优化","组合数学","排列组合"],"sample_group":[["4 3\n","8\n"],["15 5","4015"],["3050 1314","670638639"],["19198114 4154","264122135"]],"created_at":"2026-03-03 11:09:25"}}