← 返回题单
题单练习 枚举
← 上一题 下一题 →

A4992 | 平衡矩阵计数问题

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一个大小为 $n \times n$ 的 01 矩阵（矩阵元素仅为 0 或 1）。定义一个子矩阵为原矩阵中由若干连续行和列构成的矩形区域，具体来说：


  • 子矩阵由行区间 $[r_1, r_2]$（$1 \leq r_1 \leq r_2 \leq n$）和列区间 $[c_1, c_2]$（$1 \leq c_1 \leq c_2 \leq n$）唯一确定
  • 包含所有满足 $r_1 \leq i \leq r_2$ 且 $c_1 \leq j \leq c_2$ 的元素 $matrix_{i,j}$


    • 如果一个子矩阵中0的数量和1的数量相等，则称该子矩阵为「平衡子矩阵」。请计算给定矩阵中「平衡子矩阵」的总数。

    $\large{数据范围}$
  • $1 \leq n \leq 12$
  • $matrix_{i, j} \in$ {0, 1}

输入格式

第一行输入一个整数 $n$。
接下来 $n$ 行，每一行输入 $n$ 个整数，代表矩阵 $matrix$ 中的元素。

输出格式

输出一个整数占一行，表示答案。

输入输出样例

输入 #1
12
0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0
输出 #1
4320
C++ 编辑器
输入
输出