P2410 [SDOI2009] 最优图像

题目背景

小 E 在好友小 W 的家中发现一幅神奇的图画,对此颇有兴趣。

题目描述

这幅画可以被看做一个包含 $n \times m$ 个像素的黑白图像,为了方便起见,我们用 $0$ 表示白色像素,$1$ 表示黑色像素。小 E 认为这幅图画暗藏玄机,因此他记录下了这幅图像中每行、每列的黑色像素数量,以回去慢慢研究其中的奥妙。 有一天,小 W 不慎将图画打湿,原本的图像已经很难分辨。他十分着急,于是找来小 E,希望共同还原这幅图画。根据打湿后的图画,他们无法确定真正的图像,然而可以推测出每个像素原本是黑色像素的概率 $p_{i,j}\%$。那么,一个完整的图像的出现概率就可以定义为: $$\prod\limits_{i = 1}^n \prod\limits_{j = 1}^{m} p_{i, j}\% \times [s_{i, j} = 1]$$ 其中 $s_{i,j}$ 表示在还原后的图像中,像素是白色($0$)还是黑色($1$),$[s_{i, j} = 1]$ 表示若 $s_{i, j} = 1$,则该表达式的值为 $1$,否则为 $0$。换句话说,一个完整图像出现概率就等于其所有黑色像素的出现概率之积。显然,图像的黑色像素不能包含概率为 $0$ 的像素。 然而,小 E 对此也无能为力。因此他们找到了会编程的小 F,也就是你,请你根据以上信息,告诉他们最有可能是原始图像的答案是什么。

输入格式

输出格式

说明/提示

#### 样例输入输出 1 解释 共有两种可能的图像: ```plain 01 10 ``` ```plain 10 01 ``` 前者的出现概率是 $0.1×0.2=0.02$,后者的出现概率是 $0.9×0.8=0.72$,故后者是最优图像。 --- #### 数据规模与约定 - 对于 $20\%$ 的数据,保证 $n, m \leq 5$。 - 对于 $100\%$ 的数据,保证 $1 \leq n, m \leq 100$,$0 \leq p_{i, j} \leq 100$,$0 \leq a_i \leq m$,$0 \leq b_i \leq n$。 --- 感谢 @[test12345](https://www.luogu.com.cn/user/23118) 提供 spj。