题解 SP34011 【JGTLE - Jalil Got TLE】

· · 题解

这道题目的暴力可以一直优化。

首先我们来看题目的代码， 3 重循环的哪一重的循环变量与答案无关？

明显可以看出，第一层 i 循环没有任何必要，仅需在最后的答案里乘上一个 a 即可。

所以时间复杂度从 O(tabc) 降至 O(tbc) ，但是还是会TLE。怎么办呢？

我们又可以发现，第三层循还可以简化成等差数列公式，\sum^{c} _{1}=(1+2+...+c-1+c)=(c+1)\times c/2。

再来看看第二重循环，哟，这不也是个等差数列吗？

发现这个result += j * k;可以转化成result+=j*(1+c)*c/2。

我们惊喜地发现，这个j也是递增的，而且可以根据乘法分配律得知：

(a+b)c=ac+bc

倒过来：

ac+bc=(a+b)c

实际上，我们求出前面所有 j 变量的和即可。

于是，因为等差数列公式得知，前面所有 j 变量之和可以变成 (1+j)\times j \div 2

然后就变成了这样：

result=((1+b)*b/2)*((1+c)*c/2)。

于是最后时间复杂度一直简化，从O(tabc) 到 O(t)。

答案就是 a \sum^{1} _{b} \sum^{1} _{c}，即 a \times [(1+b)*b\div 2] \times [(1+c)*c\div 2] 。

细节：注意long long，末尾不要忘记乘上最后的 a！

没了。