PRoblem A. Square Counting

Description

Mr. Panda has just been given a grid with R rows and C columns of dots. How many different squares can he find in this grid? Since the number might be very large, please output the answer modulo 109 + 7 (1000000007).

Algorithm

比赛开始时取了个外卖，然后推公式推了很久。对于十二三分钟就做出来这题的人我只能表示佩服。

首先计算 R == C 的情况。

即 ∑k=1C−1(C−k)2(1+k−1)=∑k=1C−1k2(C−k) $$/sum_{k=1}^{C-1} {(C-k)}^2(1+k-1)=/sum_{k=1}^{C-1}{k^2}(C-k)$$ 整理之后用平方和公式和立方和公式可以得到 f(C,C)=C2(C2−1)12 $$f(C, C) = /frac{C^2(C^2-1)}{12}$$

然后不妨假设 R > C, 则对于多出来的每一行，需要加上的正方形有：

即需要加上 ∑k=1C−1(C−k)+(C−k)(k−1)=∑k=1C−1k(C−k) $$/sum_{k=1}^{C-1}{(C-k)+(C-k)(k-1)}=/sum_{k=1}^{C-1}{k(C-k)}$$ 整理一下，然后乘以 (R-C) 之后加到 f(C,C)$f(C, C)$ 上就是 f(R, C) 了。 答案需要模 109+7$10^9+7$，large的数据需要小心精度。我错了。结束之后发现了，改了又改还是不对，怀疑需要高精度？最后想起来python，直接写了公式求，是对的。

最后

我太弱了，3 hour 只做出来这一题的small数据。 第二题正则匹配没写好。 其他题再说吧。