#P3235. [Ahoi2013]好方的蛇

    ID: 2420 传统题 1000ms 512MiB 尝试: 243 已通过: 98 难度: 8 上传者: 标签>难度分类提高+/省选-排序与序列处理单调栈二维前缀和组合数学容斥原理贡献法CF2400

[Ahoi2013]好方的蛇

[AHOI2013] 好方的蛇

题目描述

有一天,可爱的蛇把自己变成了一个正方形,但变形时出了些差错。

她本来想变成一个 n×nn \times n 的全黑正方形,结果其中一些格子变成了白色。每个由至少两个格子组成的全黑矩形称为一条子蛇。

求有多少对不共享格子的全黑矩形,每个矩形至少包含两个格子。交换同一对中两个矩形的顺序只计一次。输出答案对 1000710007 取模后的值。

左侧框选都不合格,右侧框选都是合格的全黑矩形

输入格式

第一行一个整数 nn。

接下来 nn 行,每行一个长度为 nn 的字符串,如果是 B,那么是黑的;如果是 W,那么是白的。

输出格式

一行一个整数,表示答案。

3
BBW
BBW
BWW
5

数据规模与约定

  • 对于 100%100\% 的数据,n≤103n \leq 10^3。