[JRKSJ R7] 技巧性的块速递推

Luogu

IDLGP8933

Time1000ms

Memory128MB

DifficultyP4

2023洛谷原创深度优先搜索 DFS

一个 $n\times m$ 的棋盘，对每个格子染上黑白两色之一。询问有多少种染色方式，使得不存在横、竖、斜连续四个格子中存在至少三个相同颜色的格子，并且不存在横、竖、斜连续三个格子的颜色相同。若设棋盘的左上角为 $(1,1)$，右下角为 $(n,m)$，则称 $\{(x,y),(x+1,y),(x+2,y)\}$ 为横的连续三个格子，$\{(x,y),(x,y+1),(x,y+2)\}$ 为竖的连续三个格子、$\{(x,y),(x+1,y+1),(x+2,y+2)\}$ 和 $\{(x,y),(x+1,y-1),(x+2,y-2)\}$ 为斜的连续三个格子（以上格子均在棋盘内）。连续四个格子同理。 ## Input **本题有多组数据。** 第一行一个整数 $T$ 表示数据组数。\ 接下来 $T$ 行，每行两个整数 $n,m$ 表示一次询问。 ## Output 共 $T$ 行，每行一个整数表示答案。答案对 $998244353$ 取模。 [samples] ## Background 充分必要，切比雪夫。原来还是，不需要了。 ## Note ### 样例解释样例 $1$：显然任意染色均合法，答案为 $2^4=16$。样例 $2$： ``` 101 110 010 ``` 这是合法方案之一。 ``` 111 110 011 ``` 这是不合法方案之一，因为 $\{(1,1),(1,2),(1,3)\}$、$\{(1,2),(2,2),(3,2)\}$ 和 $\{(1,1),(2,2),(3,3)\}$ 均不满足条件。 ### 数据规模本题采用捆绑测试。 | $\text{Subtask}$ | $n,m\le$ | $\text{Score}$ | | :----------: | :----------: | :----------: | | $1$ | $30$ | $40$ | | $2$ | $10^9$ | $60$ | 对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le n,m\le 10^9$。

Samples

Input #1

1
2 2

Output #1

Input #2

1
3 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[JRKSJ R7] 技巧性的块速递推",
    "description": {
      "content": "一个 $n\\times m$ 的棋盘，对每个格子染上黑白两色之一。 询问有多少种染色方式，使得不存在横、竖、斜连续四个格子中存在至少三个相同颜色的格子，并且不存在横、竖、斜连续三个格子的颜色相同。 若设棋盘的左上角为 $(1,1)$，右下角为 $(n,m)$，则称 $\\{(x,y),(x+1,y),(x+2,y)\\}$ 为横的连续三个格子，$\\{(x,y),(x,y+1),(x,y+2)\\}$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8933"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一个 $n\\times m$ 的棋盘，对每个格子染上黑白两色之一。\n\n询问有多少种染色方式，使得不存在横、竖、斜连续四个格子中存在至少三个相同颜色的格子，并且不存在横、竖、斜连续三个格子的颜色相同。\n\n若设棋盘的左上角为 $(1,1)$，右下角为 $(n,m)$，则称 $\\{(x,y),(x+1,y),(x+2,y)\\}$ 为横的连续三个格子，$\\{(x,y),(x,y+1),(x,y+2)\\}$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments