子格计数¶

预估时间限制：1 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。

背景故事¶

一个计算模块提供两种二元运算。现在要从全部元素中保留一部分，使保留的元素经过任意一种运算后，结果仍在保留范围内。请统计可以保留的非空元素集合。

(本故事由GPT-6重写)

给定由 \(n\) 个不同元素组成的格 \(S\) ，元素编号为 \(1,\ldots,n\) .格是一个非空偏序集，其中任意两个元素都有唯一的上确界（不大于任何其他共同上界的共同上界）和下确界（不小于任何其他共同下界的共同下界）。分别记为 \(i\lor j\) 与 \(i\land j\) .

一个非空子集 \(U\subseteq S\) 是子格，当且仅当对任意 \(i,j\in U\) ，都有 \(i\lor j\in U\) 且 \(i\land j\in U\) .这些运算取给定格中的结果。求子格的数量；元素集合不同就视为不同子格，即使结构同构也分别计数。空集不计入，整个格计入。

第一行整数 \(n\) .接下来 \(n\) 行，每行 \(n\) 个整数，构成矩阵 \(A\) .若 \(i\le j\) ，则 \(A_{i,j}=i\lor j\) ；若 \(i\ge j\) ，则 \(A_{i,j}=i\land j\) .对角线两种定义一致，均为 \(i\) .

上确界与下确界本身都是交换运算；矩阵用两个三角区域分别存储它们，因此矩阵不一定对称。

输出一行一个整数，表示非空子格的个数。

8
1 1 3 7 3 6 7 6 
2 2 3 4 5 6 7 8 
1 2 3 6 3 6 6 6 
2 2 2 4 8 6 7 8 
2 2 5 2 5 6 6 8 
1 2 3 4 5 6 6 6 
1 2 1 4 2 7 7 6 
2 2 5 4 5 8 4 8

1
1

第一组共有 \(73\) 个非空子格。第二组只能选择唯一元素。第三组是三元素全序，任意非空子集都对最大值与最小值封闭，共 \(2^3-1=7\) 个。

四元素格中的一个闭合子集和一个不闭合子集

图中编号一是最小元，四是最大元，二和三互不比较。集合 \(\{1,2,4\}\) 闭合；集合 \(\{2,3\}\) 的两种运算结果分别为四和一，因此不闭合。

对所有数据，\(1\le n\le22\) ，\(1\le A_{i,j}\le n\) .保证给定运算确实来自一个格，编号大小不代表偏序中的大小关系。

分值比例	额外条件
100%	无额外条件