n*m的點陣中有多少個正方形？

01-27

包括斜的和正的
4*4 有 20 個

不失一般性假定 $Rleq C$

設左下角坐標為 $(x,y)$ ,左上角坐標為 $(x+a,y+b)$ ，右下角坐標為 $(x+b,y-a)$ ，右上角坐標為 $(x+a+b,y+b-a)$ ，其中 $ageq0, b>0$ .

因為任意橫坐標在 $[0,C)$ 中，任意縱坐標在 $[0,R)$ 中，所以我們可以列出不等式組：

$egin{cases} xgeq0\x+ageq 0 \ x+bgeq 0\x+a+bgeq 0end{cases}$ $egin{cases} x<C\x+a<C\x+b<C\x+a+b<C end{cases}$

$egin{cases} ygeq0\ y+bgeq 0 \ y-ageq 0\ y+b-ageq 0 end{cases}$ $egin{cases} y<R\ y+b<R \ y-a<R\ y+b-a<R end{cases}$

解得：

$egin{cases} 0leq x < C-a-b\ aleq y < R-b end{cases}$

那麼對於任意一組 $(a,b)$ ，在 $R imes C$ 的點陣中，這種形狀的正方形一共有 $(R-a-b)(C-a-b)$ 個。

所以答案為 $sum_{a=0}^Rsum_{b=1}^{R-a} (R-a-b)(C-a-b)$ 。

然而這個和式計算是 $O(n^2)$ 的，顯然無法快速計算。

-------------------------------------------------------------------------------------------

容易發現所有項都是 $(R-(a+b))(C-(a+b))$ 這樣的形式的。

那麼我們設 $s = (a+b)$

由於每個s都有s種拼法（例如 $s=egin{cases}3 = 0+3\3 = 1+2\3 = 2+1end{cases}$ （注意a,b的取值範圍））

那麼答案為 $sum_{s=1}^R (R-s)(C-s)s$

然而計算這個和式的複雜度是 $O(n)$ ，仍然無法解決1e9的case。

------------------------------------------------------------------------------------------

那麼現在我們來展開一下

$sum_{s=1}^R (R-s)(C-s)s = sum_{s=1}^R (RCs-(R+C)s^2+s^3)$

每一項分開計算，使用自然數冪和的公式就可以 $O(1)$ 解決了

斜的正方形其實並不難計算，如果對每個斜正方形做排斥邊界，可以發現所有邊界都是正方形

如下圖中，紅色和綠色的排斥邊界為橙色正方形

所以可以直接枚舉每個排斥邊界，並進行計數

對於 $n imes n$ 的點陣排斥邊界，所含有的正方形（正的和斜的）的個數為 $n-1$
在 $n imes m$ 的點陣中，所含有的 $k imes k$ 的排斥邊界的個數為 $(n-k+1)(m-k+1)$

UP：感謝評論區 @沐十的提醒，原表述採用了邊長而非點陣數目，公式已更正

通過這兩條結論就可以直接計算正方形的個數了

$ans = sum_{i=2}^{min(n,m)}(n-i+1)(m-i+1)(i-1)=sum_{i-1=1}^{min(n,m)-1}(n-(i-1))(m-(i-1))(i-1)$

化簡後可得

$ans=sum_{i=1}^{min(n,m)} (n-i)(m-i)i$

================ 2017.03.06 更新 ================

其實上面的結論是 $O(min(n,m))$ 複雜度的，可以繼續優化

令 $r=min(n,m)$ ，則

$ans = sum_{i=1}^{r} i^3 - (n+m)sum_{i=1}^{r} i^2 + nmsum_{i=1}^{r} i$

應用等冪求和公式

$sum _{{i=1}}^{{n}}i^{}={frac {n(n+1)}{2}}={frac {1}{2}}n^{2}+{frac {1}{2}}n$ $sum _{{i=1}}^{{n}}i^{{2}}={frac {n(n+1)(2n+1)}{6}}={frac {1}{3}}n^{3}+{frac {1}{2}}n^{2}+{frac {1}{6}}n$ $sum _{{i=1}}^{{n}}i^{{3}}=left[{frac {n(n+1)}{2}} ight]^{{2}}={frac {1}{4}}n^{4}+{frac {1}{2}}n^{3}+{frac {1}{4}}n^{2}$

最後可以優化成

$ans=({frac {1}{4}}r^{4}+{frac {1}{2}}r^{3}+{frac {1}{4}}r^{2})-(n+m)({frac {1}{3}}r^{3}+{frac {1}{2}}r^{2}+{frac {1}{6}}r)+nm({frac {1}{2}}r^{2}+{frac {1}{2}}r)$

複雜度 $O(1)$ ，解決一下大數即可

計數的關鍵是要觀察到任意一個傾斜的正方形必然唯一內接於一個非傾斜的正方形，而一個非傾斜的邊長為k的非傾斜正方形，一條邊上有k-1個內點，每個內點恰好確定一個內接於其中的傾斜正方形，加上非傾斜正方形本身，可知，將邊長為k的非傾斜正方形數目乘以k，再按k求和即可得到所有正方形的數目。

設2≤n≤m，k≤n-1，則邊長為k的非傾斜有

(n-k)(m-k)個，故所有正方形有

∑(m-k)(n-k)k個

例如m=n=4

正方形有3*3*1+2*2*2+1*1*3=20個

來填坑了，

Google Kickstart Round A 第一題。

思路是，先找出所有可能出現的正方形形狀（包括邊長、斜率），因為形狀不同，正方形一定不同。然後對於每一個形狀，求 R 行 C 列的點陣中能出現幾個。最後求和即可。

那麼如何枚舉形狀呢。

首先，任意一個正方形，只需要兩個點即可確定，為了防止重複，我們取該圖形的上沿作為特徵值，如下圖中正方形的紅色邊：