{"problem":{"name":"[NOIP2022] 种花","description":{"content":"小 C 决定在他的花园里种出 $\\texttt{CCF}$ 字样的图案，因此他想知道 $\\texttt C$ 和 $\\texttt F$ 两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种花，因此他希望你能帮助他解决这个问题。 花园可以看作有 $n\\times m$ 个位置的网格图，从上到下分别为第 $1$ 到第 $n$ 行，从左到右分别为第 $1$ 列到第 $m$ 列，","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8865"},"statements":[{"statement_type":"Markdown","content":"小 C 决定在他的花园里种出 $\\texttt{CCF}$ 字样的图案，因此他想知道 $\\texttt C$ 和 $\\texttt F$ 两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种花，因此他希望你能帮助他解决这个问题。\n\n花园可以看作有 $n\\times m$ 个位置的网格图，从上到下分别为第 $1$ 到第 $n$ 行，从左到右分别为第 $1$ 列到第 $m$ 列，其中每个位置有可能是土坑，也有可能不是，可以用 $a_{i,j} = 1$ 表示第 $i$ 行第 $j$ 列这个位置有土坑，否则用 $a_{i,j} = 0$ 表示这个位置没土坑。\n\n一种种花方案被称为 $\\texttt{C-}$ **形**的，如果存在 $x_1, x_2 \\in [1, n]$，以及 $y_0, y_1, y_2 \\in [1, m]$，满足 $x_1 + 1 < x_2$，并且 $y_0 < y_1, y_2 \\leq m$，使得第 $x_1$ **行**的第 $y_0$ 到第 $y_1$ **列**、第 $x_2$ **行**的第 $y_0$ 到第 $y_2$ **列**以及第 $y_0$ **列**的第 $x_1$ 到第 $x_2$ **行**都**不为土坑**，且只在上述这些位置上种花。\n\n一种种花方案被称为 $\\texttt{F-}$ **形**的，如果存在 $x_1, x_2, x_3 \\in [1, n]$，以及 $y_0, y_1, y_2 \\in [1, m]$，满足 $x_1 + 1 < x_2 < x_3$，并且 $y_0 < y_1, y_2 \\leq m$，使得第 $x_1$ **行**的第 $y_0$ 到第 $y_1$ **列**、第 $x_2$ **行**的第 $y_0$ 到第 $y_2$ **列**以及第 $y_0$ **列**的第 $x_1$ 到第 $x_3$ **行**都**不为土坑**，且只在上述这些位置上种花。\n\n样例一解释中给出了 $\\texttt{C-}$ 形和 $\\texttt{F-}$ 形种花方案的图案示例。\n\n现在小 C 想知道，给定 $n, m$ 以及表示每个位置是否为土坑的值 $\\{a_{i,j}\\}$，$\\texttt{C-}$ 形和 $\\texttt{F-}$ 形种花方案分别有多少种可能？由于答案可能非常之大，你只需要输出其对 $998244353$ 取模的结果即可，具体输出结果请看输出格式部分。\n\n## Input\n\n第一行包含两个整数 $T, id$，分别表示数据组数和测试点编号。如果数据为样例则保证 $id = 0$。\n\n接下来一共 $T$ 组数据，在每组数据中：\n\n第一行包含四个整数 $n, m, c, f$，其中 $n, m$ 分别表示花园的行数、列数，对于 $c, f$ 的含义见输出格式部分。\n\n接下来 $n$ 行，每行包含一个长度为 $m$ 且仅包含 $0$ 和 $1$ 的字符串，其中第 $i$ 个串的第 $j$ 个字符表示 $a_{i,j}$，即花园里的第 $i$ 行第 $j$ 列是不是一个土坑。\n\n## Output\n\n设花园中 $\\texttt{C-}$ 形和 $\\texttt{F-}$ 形的种花方案分别有 $V_C$ 和 $V_F$ 种，则你需要对每一组数据输出一行用一个空格隔开的两个非负整数，分别表示 $(c \\times V_C) \\bmod 998244353$，$(f \\times V_F ) \\bmod 998244353$ ，其中 $a \\bmod P$ 表示 $a$ 对 $P$ 取模后的结果。\n\n[samples]\n\n## Note\n\n**【样例 1 解释】**\n\n四个 $\\texttt{C-}$ 形种花方案为：\n\n```plain\n**1 **1 **1 **1\n*10 *10 *10 *10\n**0 *** *00 *00\n000 000 **0 ***\n```\n\n其中 $\\texttt*$ 表示在这个位置种花。注意 $\\texttt C$ 的两横可以不一样长。\n\n类似的，两个 $\\texttt{F-}$ 形种花方案为：\n\n```plain\n**1 **1\n*10 *10\n**0 ***\n*00 *00\n```\n\n**【样例 2】**\n\n见附件下的 $\\texttt{plant/plant2.in}$ 与 $\\texttt{plant/plant2.ans}$。\n\n**【样例 3】**\n\n见附件下的 $\\texttt{plant/plant3.in}$ 与 $\\texttt{plant/plant3.ans}$。\n\n**【数据范围】**\n\n对于所有数据，保证：$1 \\leq T \\leq 5$，$1 \\leq n, m \\leq 10^3$，$0 \\leq c, f \\leq 1$，$a_{i,j} \\in \\{0, 1\\}$。\n\n| 测试点编号 | $n$ | $m$ | $c=$ | $f=$ | 特殊性质 | 测试点分值 |\n| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |\n| $1$ | $\\leq 1000$ | $\\leq 1000$ | $0$ | $0$ | 无 | $1$ |\n| $2$ | $=3$ | $=2$ | $1$ | $1$ | 无 | $2$ |\n| $3$ | $=4$ | $=2$ | $1$ | $1$ | 无 | $3$ |\n| $4$ | $\\leq 1000$ | $=2$ | $1$ | $1$ | 无 | $4$ |\n| $5$ | $\\leq 1000$ | $\\leq 1000$ | $1$ | $1$ | A | $4$ |\n| $6$ | $\\leq 1000$ | $\\leq 1000$ | $1$ | $1$ | B | $6$ |\n| $7$ | $\\leq 10$ | $\\leq 10$ | $1$ | $1$ | 无 | $10$ |\n| $8$ | $\\leq 20$ | $\\leq 20$ | $1$ | $1$ | 无 | $6$ |\n| $9$ | $\\leq 30$ | $\\leq 30$ | $1$ | $1$ | 无 | $6$ |\n| $10$ | $\\leq 50$ | $\\leq 50$ | $1$ | $1$ | 无 | $8$ |\n| $11$ | $\\leq 100$ | $\\leq 100$ | $1$ | $1$ | 无 | $10$ |\n| $12$ | $\\leq 200$ | $\\leq 200$ | $1$ | $1$ | 无 | $6$ |\n| $13$ | $\\leq 300$ | $\\leq 300$ | $1$ | $1$ | 无 | $6$ |\n| $14$ | $\\leq 500$ | $\\leq 500$ | $1$ | $1$ | 无 | $8$ |\n| $15$ | $\\leq 1000$ | $\\leq 1000$ | $1$ | $0$ | 无 | $6$ |\n| $16$ | $\\leq 1000$ | $\\leq 1000$ | $1$ | $1$ | 无 | $14$ |\n\n特殊性质 A：$\\forall 1 \\leq i \\leq n, 1 \\leq j \\leq \\left\\lfloor \\frac{m}{3} \\right\\rfloor$，$a_{i, 3 j} = 1$；\n\n特殊性质 B：$\\forall 1 \\leq i \\leq \\left\\lfloor \\frac{n}{4} \\right\\rfloor, 1 \\leq j \\leq m$，$a_{4 i, j} = 1$；","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8865","tags":["数学","2022","NOIP 提高组","O2优化","枚举","组合数学","前缀和"],"sample_group":[["1 0\n4 3 1 1\n001\n010\n000\n000","4 2"]],"created_at":"2026-03-03 11:09:25"}}