{"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)\\}$ 为竖的连续三个格子、$\\{(x,y),(x+1,y+1),(x+2,y+2)\\}$ 和 $\\{(x,y),(x+1,y-1),(x+2,y-2)\\}$ 为斜的连续三个格子（以上格子均在棋盘内）。\n\n连续四个格子同理。\n\n## Input\n\n**本题有多组数据。**\n\n第一行一个整数 $T$ 表示数据组数。\\\n接下来 $T$ 行，每行两个整数 $n,m$ 表示一次询问。\n\n## Output\n\n共 $T$ 行，每行一个整数表示答案。答案对 $998244353$ 取模。\n\n[samples]\n\n## Background\n\n充分必要，切比雪夫。\n\n原来还是，不需要了。\n\n## Note\n\n### 样例解释\n\n样例 $1$：显然任意染色均合法，答案为 $2^4=16$。\n\n样例 $2$：\n\n```\n101\n110\n010\n```\n\n这是合法方案之一。\n\n```\n111\n110\n011\n```\n\n这是不合法方案之一，因为 $\\{(1,1),(1,2),(1,3)\\}$、$\\{(1,2),(2,2),(3,2)\\}$ 和 $\\{(1,1),(2,2),(3,3)\\}$ 均不满足条件。\n\n### 数据规模\n\n本题采用捆绑测试。\n| $\\text{Subtask}$ | $n,m\\le$ | $\\text{Score}$ |\n| :----------: | :----------: | :----------: | \n| $1$ | $30$ | $40$ |\n| $2$ | $10^9$ | $60$ |\n\n对于 $100\\%$ 的数据，$1\\le T\\le 10^5$，$1\\le n,m\\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8933","tags":["2023","洛谷原创","深度优先搜索 DFS"],"sample_group":[["1\n2 2","16"],["1\n3 3","32"]],"created_at":"2026-03-03 11:09:25"}}