2020牛客国庆集训派对day2 F

来自【比赛题解】 649 浏览 0 回复 2020-10-14

__故人__

+关注

SUM OF SUB RECTANGLE AREAS

https://ac.nowcoder.com/acm/contest/7818/F

题意

$ans=\sum_{i=0}^{N-1}\sum_{j=i+1}^{N}\sum_{a=0}^{N-1}\sum_{b=a+1}^{N}(j-i)\times (b-a)$

分析

开放式求和 $ans=(\sum_{i=0}^{N-1}\sum_{j=i+1}^{N}(j-i))^2$ 推导之后 $ans^{\frac{1}{2}}=\sum_{i=0}^{N-1}\frac{i^2+i}{2}=\frac{n(2n+1)(n+1)}{6}+\frac{n(n+1)}{2}$ 。因为偷懒，直接上 $python$ 了。

代码

T=int(input())
for i in range(T):
    n=int(input())
    b= ((n*(2*n+1)*(n+1))//6 + (n*(n+1))//2)//2
    print(b**2)