洛谷P2241 统计方形(数据加强版)

P2241 统计方形(数据加强版)

一般地设(n<=m)

设正方形个数为(x),长方形个数为(y)

[x=sum_{i=1}^{n}(n-i+1)(m-i+1) ]

[x=sum_{i=1}^{n}(nm-mi+m-ni+i^2-i+n-i+1) ]

[x=n(nm+m+n+1)sum_{i=1}^{n}(i^2-(m+n+2)i) ]

[x=n(nm+m+n+1)+frac{n(n+1)(2n+1)}{6}-(m+n+2)frac{n(1+n)}{2} ]

[x+y=dbinom{n+1}{2}dbinom{m+1}{2} ]

原文地址:https://www.cnblogs.com/knife-rose/p/15005744.html