{"problem":{"name":"[PA 2022] Bakterie","description":{"content":"**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 5 [Bakterie](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/bak/)** Albert Bynstein 教授目前正在研究一种新发现的细菌菌株，他给它起了一个代号叫 *Algorithmic Proeli","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":10000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9263"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 5 [Bakterie](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/bak/)**\n\nAlbert Bynstein 教授目前正在研究一种新发现的细菌菌株，他给它起了一个代号叫 *Algorithmic Proeliis*。在他的下一个实验中，他准备了一个大的矩形实验台，他将其分为 $n\\cdot m$ 个区域，排列成 $n$ 行，每行 $m$ 个区域。\n\n然后对于每个区域，教授将从三个选项中选择一个：要么他一定会在其中放置一个培养皿，要么他一定不放培养皿，要么他将抛出一枚均匀的硬币来决定放不放培养皿。一旦培养皿放置完毕，为了进行实验就需要选择一个正整数 $k$，并在每个培养皿里放置恰好 $k$ 个细菌。\n\n这种细菌的特点是十分敌视其他菌落，因此实验过程如下：只要有一对相邻的、非空的培养皿，就会随机选出一对这样的培养皿（概率分布相等），之后两个培养皿中各有一个细菌死亡。我们假定，当且仅当两个培养皿所处的区域有一条公共边时，两区域相邻。\n\n考虑到抛硬币决定将培养皿放在某些区域里的随机性，和选择相邻培养皿并让其中的细菌死亡的随机性，令 $f(k)$ 表示在整个实验中存活的细菌的期望数量。显然，当不再有一对相邻的培养皿各含有至少一个细菌时，实验就会结束。\n\n一次在培养皿里放几个细菌很难，但一次性放置很多细菌就会容易得多。为此，教授沉思了一下，然后在黑板上写下了如下表达式：\n$$\n\\lim_{k\\to \\infty}\\frac{f(k)}{k}\n$$\n你作为他的助手，任务是计算上述极限的值。可以证明这个值总是一个可测的数字，所以你需要用一个不可约分数的形式表达这个值。\n\n## Input\n\n输入第一行包含两个整数 $n,m$，表示这个矩形实验台的大小。\n\n接下来 $n$ 行描述试验台。第 $i$ 行包含 $m$ 个字符，第 $j$ 个字符记为 $a_{i,j}$。如果 $a_{i,j}$ 是 `.`，则第 $i$ 行的第 $j$ 个区域一定不放培养皿。如果 $a_{i,j}$ 是 `O`（大写的 `o`），则第 $i$ 行的第 $j$ 个区域一定放培养皿。如果 $a_{i,j}$ 是 `?`，则第 $i$ 行的第 $j$ 个区域会用投硬币的方式决定放不放培养皿。\n\n## Output\n\n输出一行，表示对教授问题的回答。按 $a/b$ 的形式输出，其中 $b\\ge 1$ 且 $\\gcd(a,b)=1$。\n\n[samples]\n\n## Note\n\n对于 $100\\%$ 的数据，满足：\n\n$1\\le n,m\\le 200$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9263","tags":["2022","PA（波兰）"],"sample_group":[["4 5\nO...O\n?OO.?\n.OOO.\n?..O.\n","5/2\n"]],"created_at":"2026-03-03 11:09:25"}}