￥## 題目鏈接 https://code.google.com/codejam/contest/8284486/dashboard

題意

給一個(gè)m?n$m /cdot n$的格點(diǎn)圖，求這個(gè)格點(diǎn)圖中正方形的數(shù)目。

思路

包括正正方形和斜正方形。

正正方形數(shù)目

我們用f(i)$f(i)$表示邊長(zhǎng)為i$i$的正方形數(shù)目。

明顯可知f(1)=mn$f(1) = mn$，我們推一下f(2),f(3)...$f(2), f(3) ...$。

設(shè)如下格點(diǎn)圖的長(zhǎng)為m，寬為n（設(shè)m≥n$m /geq n$）： 首先我們選定左上角的邊長(zhǎng)為2的正方形。

于是我們可知f(2)=(m?1)(n?1)$f(2) = (m - 1)(n - 1)$

同理可以推得f(3)=(m?2)(n?2)$f(3) = (m - 2)(n - 2)$, f(4)=(m?3)(n?3)$f(4) = (m - 3)(n - 3)$, f(n)=(m?(n?1))(n?(n?1))$f(n) = (m - (n - 1))(n - (n - 1))$

所以我們正正方形的數(shù)目：

ans1=f(1)+f(2)+...+f(n)$ans1 = f(1) + f(2) + ... + f(n)$

? =∑i=1n(m?(i?1))(n?(i?1))$= /sum/limits_{i = 1}^{n}{(m - (i - 1))(n - (i - 1))}$

? =∑i=0n?1(m?i)(n?i)$= /sum/limits_{i = 0}^{n - 1}{(m - i)(n - i)}$

? = n(n+1)(3m?n+1)6$/frac{n(n +1)(3m - n + 1)}{6}$

斜正方形數(shù)目

首先，假設(shè)我們已經(jīng)有一個(gè)i?i$i /cdot i$的正正方形了，那么正正方形中的最大斜正方形（表示其不能再增大）有多少個(gè)呢？我們?cè)O(shè)g(i)$g(i)$為邊長(zhǎng)為i的正正方形數(shù)目包含的最大斜正方形數(shù)目。

假設(shè)i=2$i = 2$：g(i)=1$g(i) = 1$

假設(shè)i=3$i = 3$：g(i)=2$g(i) = 2$

其實(shí)觀察可知：在邊長(zhǎng)為i?i$i /cdot i$的正正方形里面，最大斜正方形的數(shù)目g(i)=i?1$g(i) = i - 1$（選定一條邊，除去最兩邊的2個(gè)點(diǎn)，其他點(diǎn)都有最大斜正方形）。

那么，我們每個(gè)邊長(zhǎng)為i?i$i /cdot i$的正正方形里面都有g(i)$g(i)$個(gè)斜正方形，我們邊長(zhǎng)為i$i$的正正方形有f(i)$f(i)$個(gè)，那么所有的斜正方形數(shù)目為：

ans2=f(1)g(1)+f(2)g(2)+...+f(n)g(n)$ans2 = f(1)g(1) + f(2)g(2) + ... + f(n)g(n)$

? =∑i=1nf(i)g(i)$= /sum/limits_{i = 1}^{n}{f(i)g(i)}$

? =∑i=0n?1f(i)g(i)$=/sum/limits_{i = 0}^{n - 1}{f(i)g(i)}$

? =∑i=0n?1(m?i)(n?i)(i?1)$= /sum/limits_{i = 0}^{n - 1}{(m - i)(n - i)(i - 1)}$

? =n(2m?n)(n+1)(n?1)12$=/frac{n(2m - n)(n+1)(n - 1)}{12}$

所以我們最后的結(jié)果為：n(n+1)(3m?n+1)6+n(2m?n)(n+1)(n?1)12$/frac{n(n +1)(3m - n + 1)}{6}+/frac{n(2m - n)(n+1)(n - 1)}{12}$

代碼