1.4 KiB
1.4 KiB
黑色矩形
题目描述
一个 n\times n 的黑白网格。定义黑色矩形为：
- 矩形由至少2个格子构成，且构成矩形的格子都为黑色
现在你要选择2个不重叠（没有公共格子）的黑色矩形，问有多少种方案，对 1e4+7 取模。2种方案不同，当且仅当选择的黑色矩形集合不同。
左图是2个不是黑色举行的例子；右图是3个是黑色矩形的例子。
参见样例1解释。
输入格式
第一行1个整数 n
接下来 n 行，每行1个长度为 n 的01串，1 代表黑色，0 代表白色。
输出格式
输出1个整数代表答案，对 1e4+7 取模。
样例 #1
样例输入 #1
2
11
11
样例输出 #1
2
样例 #2
样例输入 #2
3
110
110
100
样例输出 #2
5
样例 #3
样例输入 #3
5
01100
00100
01100
00000
11000
样例输出 #3
8
样例 #4
样例输入 #4
见下发文件
样例输出 #4
见下发文件
提示
样例1解释
共两种方案：选择第1行和第2行，或者选择第1列和第2列
数据范围
对于所有数据，1\le n \le 1500
subtask1(20pts)：n\le 10
subtask2(20pts)：n\le 50
subtask3(20pts)：n\le 500
subtask4(10pts)：网格中全部为黑色
subtask5(30pts)：无特殊限制