「KDOI-02」一个仇的复

Luogu

IDLGP8594

Time3000ms

Memory512MB

DifficultyP6

数学2022洛谷原创O2优化组合数学排列组合

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

Samples

Input #1

4 3

Output #1

Input #2

15 5

Output #2

Input #3

3050 1314

Output #3

670638639

Input #4

19198114 4154

Output #4

264122135

API Response (JSON)

{
  "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$。射线十分强力，只需一发便可与作用范围平面内的所有物体相湮灭。不过，只要宇宙射线的一部分作用范围落到目标外，便会一直...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments