「PMOI-5」破译

Luogu
IDLGP8152
Time1000ms
Memory128MB
DifficultyP1
lhm 现在有一个边长为 $1$ 的正方形,现在要进行 $k$ 次分割,每次分割需要把位于图形中右下角的矩形继续分割成 $n \times n$ 的矩形。分割完成后所有矩形的个数即为破译后的答案。lhm 需要聪明的你帮助他解决这个问题。 注:由于题面形容比较困难,请移步至样例解释便于理解题意。 ## Input 输入数据共一行。 一行两个整数 $n,k$,含义如题目所示。 ## Output 输出格式共一行。 一行一个整数,表示最终答案。 由于答案可能过大,请把答案取模 $998244353$ 后输出。 [samples] ## Background 2077 年,穿越的 Lanuxhem 为与 2021 年的 Silver187 联系,发明了一种图形转数字的密码。 ## Note ### 样例解释 对于样例 #1,进行 $2$ 次分割,每次将右下角矩形分割为 $2\times 2$ 的矩形。 第一次分割,由于只有一个矩形,所以右下角矩形即为此矩形。分割前后如下: ![](https://cdn.luogu.com.cn/upload/image_hosting/tdlnmb52.png) 变为 ![](https://cdn.luogu.com.cn/upload/image_hosting/cyemqw87.png) 接下来进行第二次分割,将右下角矩形进行分割,分割为如下图形: ![](https://cdn.luogu.com.cn/upload/image_hosting/9n3c3te2.png) 此图形包含 $7$ 个矩形,因此答案为 $7$。 ### 数据规模与约定 对于 $10\%$ 的数据,$k=1$。 对于另 $20\%$ 的数据,$1 \leq n,k \leq 10$。 对于 $100\%$ 的数据,$1 \leq n,k \leq 10^9$。 --- $2022.7.10$:新增加一组 $\text{Hack}$ 数据。
Samples
Input #1
2 2
Output #1
7
Input #2
5 3
Output #2
73
API Response (JSON)
{
  "problem": {
    "name": "「PMOI-5」破译",
    "description": {
      "content": "lhm 现在有一个边长为 $1$ 的正方形,现在要进行 $k$ 次分割,每次分割需要把位于图形中右下角的矩形继续分割成 $n \\times n$ 的矩形。分割完成后所有矩形的个数即为破译后的答案。lhm 需要聪明的你帮助他解决这个问题。 注:由于题面形容比较困难,请移步至样例解释便于理解题意。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8152"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "lhm 现在有一个边长为 $1$ 的正方形,现在要进行 $k$ 次分割,每次分割需要把位于图形中右下角的矩形继续分割成 $n \\times n$ 的矩形。分割完成后所有矩形的个数即为破译后的答案。lhm 需要聪明的你帮助他解决这个问题。\n\n注:由于题面形容比较困难,请移步至样例解释便于理解题意。\n\n## Input\n\n输入数据共一行。      \n一行两个整数 $n,k$,含义如题目所示。\n\n##...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments