{"problem":{"name":"[SNCPC2024] 表达式矩阵","description":{"content":"一个 $n \\times m$ 的字符矩阵 $a_{ij}$，被称为合法的表达式矩阵，当且仅当其满足如下条件： - 矩阵只包含 '1'，'+'，'*' 字符。 - 对于矩阵的每行从左向右组成的字符串，均为合法的表达式。 - 对于矩阵的每列从上向下组成的字符串，均为合法的表达式。 一个合法的表达式矩阵的权值定义为，每行从左向右组成的字符串和每列从上向下组成的字符串共 $n + 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":"LGP10692"},"statements":[{"statement_type":"Markdown","content":"一个 $n \\times m$ 的字符矩阵 $a_{ij}$，被称为合法的表达式矩阵，当且仅当其满足如下条件：\n\n- 矩阵只包含 '1'，'+'，'*' 字符。\n\n- 对于矩阵的每行从左向右组成的字符串，均为合法的表达式。\n\n- 对于矩阵的每列从上向下组成的字符串，均为合法的表达式。\n\n一个合法的表达式矩阵的权值定义为，每行从左向右组成的字符串和每列从上向下组成的字符串共 $n + m$ 个表达式求值后的值求和的结果。\n\n求所有 $n \\times m$ 的合法表达式矩阵中，权值最小的那一个。如果有多个最小的答案，你可以给出任意一个。\n\n我们定义字符串 $s$ 是合法表达式如下：\n\n- 如果 $s = \\overbrace{111\\dots111}^{\\text{至少一个 }1}$，则 $s$ 是合法表达式。\n\n- 如果 $s$ 和 $t$ 均为合法表达式，则 $s$ * $t$ 也是合法表达式。\n\n- 如果 $s$ 和 $t$ 均为合法表达式，则 $s$ + $t$ 也是合法表达式。\n\n## Input\n\n输入仅一行两个整数 $n, m$ ($3 \\leq n, m \\leq 9$)，由空格隔开，为矩阵的行数和列数。\n\n## Output\n\n输出共 $n$ 行，每行 $m$ 个字符，其中第 $i$ 行的第 $j$ 个字符为 $a_{ij}$，为权值最小的矩阵。\n\n如果有多个最小的答案，你可以给出任意一个。\n\n[samples]\n\n## Note\n\n对于样例，此时矩阵的权值为 $4488$，可以证明不存在权值更小的矩阵。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10692","tags":["搜索","2024","Special Judge","O2优化","陕西","省赛/邀请赛","状压 DP"],"sample_group":[["4 4\n","1111\n1*11\n11*1\n1111\n"]],"created_at":"2026-03-03 11:09:25"}}