《矩形计数》题目分析

这道题是一道用容斥原理计数的问题。

举个例子，假设K=3，也就是说有3个黑色的单位正方形，我们不妨设这三个黑色单位正方形是A，B和C。

那么，答案 = 所有矩形的数目 
           - 包含A的矩形数目 - 包含B的矩形数目 - 包含C的矩形数目  
           + 包含AB的矩形数目 + 包含BC的矩形数目 + 包含CA的矩形数目
           - 包含ABC的矩形数目

于是我们要解决的问题简化为：对于任意黑色单位正方形的集合S，如何计算包含S的矩形数目。

我们知道只要确定矩形上边界、下边界、左边界和右边界的位置，就唯一确定了一个矩形。

对于给定的黑色单位正方形集合S，不难发现，如果要一个矩形包含S中所有的黑色单位正方形，那么这个矩形的左边界一定在最靠左的黑色单位方形左边(或者与其左边界重合)。

同理这个矩形的右边界一定在最靠右的黑色单位方形有边(或者与其上边界重合)。

这个矩形的上边界一定在最靠上的黑色单位方形上边(或者与其上边界重合)。

同理这个矩形的下边界一定在最靠下的黑色单位方形下边(或者与其下边界重合)。

如上图所示，如果要包含3个黑色单位正方形。则左边界要在蓝色线左边(或重合，有2种可能)，右边界在橘色线右边(或重合，有2种可能)，上边界在绿色线上边(或重合，有2种可能)，下边界在红色线下边(或重合，有2种可能)。

所以这样的矩形数目总共有2x2x2x2=16个。