还是决定报名一下APIO，毕竟不想留下遗憾。没报CTS。
刷水题.jpg
题意描述
f(n)的定义为:f(n)=1^3+2^3+3^3+…+n^3，所以它是所有自然数到n的立方的和。
在这个问题中，你要计算，f(1) + f(2) + f(3) +…+ f (n)
输入输出格式
输入格式
第一行是一个整数T(1≤T≤100000),表示测试用例的数量。接下来是T个测试用例。对于每个测试用例,都有一个整数n (1≤n≤1000000)，写在一行。
输出格式
对于每个测试用例，输出上述算式的结果。
由于这个数字可能非常大，因此输出答案模1 000,000,003。
输入输出样例
输入样例#1：
1 | 3 |
输出样例#1：
1 | 10 |
题目背景
题意翻译：
定义f(n)=\sum\limits{i=1}^ni^3f(n)=i=1∑n**i3
你需要求出\sum\limits{i=1}^nf(i)i=1∑n**f(i)
将答案对10000000031000000003取模。
输入格式：
一行一个正整数TT，接下来TT行，每行一个正整数nn
输出格式：
TT行，每行一个正整数表示答案
题目描述
f(n) is defined as: $f(n) = 1 ^{3} +2 ^{3} +3 ^{3} +…+n ^{3}$ , so it is the sum of the cubes of all natural numbers up to n.
In this problem you are about to compute,
$f(1) + f(2) + f(3) + … + f(n)$
输入输出格式
输入格式：
The first line is an integer T(1 T T test cases follow.
For each test case, there is an integer n(1 n
输出格式：
For each test case output the result of the summatory function described above.
Since this number could be very large, output the answer modulo 1,000,000,003.
输入输出样例
输入样例#1：
1 | \n3\n2\n10\n3\n\n |
输出样例#1：
1 | \n10\n7942\n46 |
Solution
A introduction of Equal power summation
Well , this problem is very easy if you use linear recurrence.
First we need to learn how to calculate the sum of pow !
Let’s start !
first we calculate
$\sum_{i=1}^{n}i^2$
Lemma :
$(i+1)^3-i^3$
$=3i^2+3i+1$
⇒
$i^2 = \frac{(i+1)^3-i^3-3i-1}{3}$
∴
$\sum{i=1}^{n}i^2$
$ = \sum{i=1}^{n}(i+1)^3-i^3-3i-1$
$=\frac{(n+1)^3-1-3\sum_{i=1}^{n}-n}{3}$
$=\frac{n(n+1)(2n+1)}{6}$
∴
$\sum\limits_{i=1}^{n}i^3$
$=\frac{(n+1)^4-1-6\sum\limits{i=1}^{n}i^2-4\sum\limits{i=1}^{n}i-\sum\limits_{i=1}^{n}1}{4}$
$=\frac{(n+1)^4-1-n(n+1)(2n+1)-2n(n+1)-n}{4}$
$=\frac{(n+1)[(n+1)^3-1-n(2n+1)-2n]}{4}$
$=\frac{n^2(n+1)^2}{4}$
Cubic sum finished , but haven’t done yet.
Like above , $\sum\limits_{i=1}^{n}i^4 = 1/5n^5+1/2n^4+1/3n^3-1/30n$
Actually , we could easily extended to $k$ power sum based on Binomial theorem.
And we could use recurrence or explicit expression to write the formula.
explicit expresssion:
$Sm(n) = \frac{1}{m+1}\sum{k=0}^{m}\binom{m+1}{k}B_kn^{m+1-k}$
$B_i$ means Bernulli numbers , which could be calculated by recurrence.
$\sum{i=0}^{m}\binom{m+1}{i}B{i}=0$
$B_0 = 1$
In the concrete calculation before , we found the new sum $Sk(n)$ is relevant to the $S{k-1}(n)$
by calculating , we found:
$Sk(x) = \frac{1}{k+1}\{(x+1)^{n+1}-\sum\limits{i=2}^{k}\binom{k+1}{i}S_{k+1-i}(n)-x-1\}$
(actually it is also could be found by your eyes)
Well , this problem answer is :
$\sum_{i=1}^{n}\frac{n^2(n+1)^2}{4}$
$=O(n^4)$
As we know before , the answer formula is composed by the formula above . could be solve $O(1)$.
QWQ..