寻宝(Treasure)

Luogu
IDLGP8559
Time2000ms
Memory256MB
DifficultyP7
数学递推莫队洛谷原创O2优化生成函数高斯消元
铃准备到一个 $2$ 行 $n+1$ 列的方格图上寻宝。 有这样寻宝的机会,她不会放过任何一个可以获取的宝物。 每个方格都有两种状态:**空地** 或 **墙壁**。 **空地** 可以被自由穿过,除了第一列的下面都埋藏有宝物,地图的第一列一定是空地,也是地图的入口。 **墙壁** 不能被穿过。 需要注意的是,她每次只能移动到相邻的方格,且地图的边界也是不能被穿过的。 铃还不知道地图的形态,正在考虑策略时,澪说:「我知道地图中恰好有 $k$ 个墙壁哦,对于所有可能的地图,有多少种情况你能找到恰好 $m$ 个宝物呢?」 「那我不回答又怎样嘛。」铃只想着挖宝,轻浮地答道。 「欸?那还有好几个藏宝点我就不告诉你了~」澪表现出一副认真的样子,「不过我也不难为你,你求出答案对 $998244353$ 取模的结果就可以啦。」 铃没有办法,只能请你帮忙算出答案。 ## Input 仅一行三个正整数 $n,k,m$。 ## Output 仅一行一个整数表示答案。 [samples] ## Note 【样例一解释】 地图大小为 $2\times(3+1)$,有 $3$ 个障碍。其中有 $4$ 种情况可以找到恰好 $2$ 个宝物,具体如下: ![](https://cdn.luogu.com.cn/upload/image_hosting/rd7xxuhd.png) 图中绿色的部分表示入口,灰色表示墙壁,白色代表**有宝藏的**空地。 可以看出,有且仅有图中 $4$ 种情况可以由入口走到恰好 $2$ 块空地上,即获得 $2$ 个宝物。 故答案为 $4$。 【数据范围】 **本题采用捆绑测试。** Subtask1(11 pts):$n\leq 12$; Subtask2(19 pts):$n\leq 1000$; Subtask3(31 pts):$n \leq 5\times 10^4$; Subtask4(39 pts):无特殊限制。 对于 $100\%$ 的数据,$2\le n \le 3\times 10^6$,$m,k\geq 2$,$m+k\leq 2n$。 【提示】 这是一道 OI 题,不是证明题。
Samples
Input #1
3 3 2
Output #1
4
Input #2
10 9 11
Output #2
776
Input #3
10 8 7
Output #3
6776
Input #4
233 123 114
Output #4
22504357
API Response (JSON)
{
  "problem": {
    "name": "寻宝(Treasure)",
    "description": {
      "content": "铃准备到一个 $2$ 行 $n+1$ 列的方格图上寻宝。    有这样寻宝的机会,她不会放过任何一个可以获取的宝物。 每个方格都有两种状态:**空地** 或 **墙壁**。 **空地** 可以被自由穿过,除了第一列的下面都埋藏有宝物,地图的第一列一定是空地,也是地图的入口。 **墙壁** 不能被穿过。 需要注意的是,她每次只能移动到相邻的方格,且地图的边界也是不能被穿过的。 铃还不知道地",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8559"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "铃准备到一个 $2$ 行 $n+1$ 列的方格图上寻宝。   \n有这样寻宝的机会,她不会放过任何一个可以获取的宝物。\n\n每个方格都有两种状态:**空地** 或 **墙壁**。\n\n**空地** 可以被自由穿过,除了第一列的下面都埋藏有宝物,地图的第一列一定是空地,也是地图的入口。\n\n**墙壁** 不能被穿过。\n\n需要注意的是,她每次只能移动到相邻的方格,且地图的边界也是不能被穿过的。\n\n铃还不知道地...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments