uva 10177 - (2/3/4)-D Sqr/Rects/Cubes/Boxes?

这是一道数学题吧。想清楚之后就发现就是求累加和。
问题是给定一个正方形(体,超体),求其中的所有的正方形(体,超体),长方形(体,超体)。 比如,4 * 4的正方形中,有14个正方形,22个长方形,4 * 4 * 4的立方体中有36个正方体,180个长方体。依次类推,超正方体指的是四维空间。
观察一下一个44正方形中,仔细验证一下就会发现,正方形的个数是 Σ(4 - i + 1) * (4 - i + 1)(其中i从1到4),长方形的个数是Σ(4 - i + 1) (其中j从1到4) * Σ(4 - j + 1)(其中j从1到4)。如果变成3维的就多一层k,k也从1变化到4。如果变成4维的就再多一层l,l也从1变化到4。
然后变换一下,就可以得到s2(n) = 1^1 + 2^2 + … + n^n,s3(n)则是对立方的累加和,s4(n)则是对四次方的累加和。
再计算r2(n)。可以先把正方形包括在内计算出所有的和。那么r2(n) = Σ(n - i + 1) * Σ(n - j + 1) - s2(n)。如果直接进行这个式子的求和话很复杂。再观察一下这个式子,因为n - i + 1的变化范围就是1到n,那么上面的式子可以变化为 r2(n) = ΣΣi * j - s2(n)。意思是求i
j的和,i和j都是从1变化到n。很简单就可以得到r2(n) = pow(n * (n + 1) / 2, 2) - s2(n)。同样的求和可以得到,r3(n) = pow(n * (n + 1) / 2, 3) - s3(n)。r4(n) = pow(n * (n + 1) / 2, 4) - s4(n)。
另外如果不知道平方和,立方和,四次方和的公式,也可以迭代计算,复杂度也是O(100)。这样的话,根本不需要使用这些难记忆的公式了。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h> 
#include <math.h>
unsigned long long s2[101];
unsigned long long r2[101];
unsigned long long s3[101];
unsigned long long r3[101];
unsigned long long s4[101];
unsigned long long r4[101];

int main()
{
unsigned long long i = 0;
while (i <= 100)
{
s2[i] = i * (i + 1) * (2 * i + 1) / 6;//平方和
s3[i] = i * i * (i + 1) * (i + 1) / 4;//立方和
s4[i] = i * (i + 1) * (6 * i * i * i + 9 * i * i + i - 1) / 30;//四次方和
r2[i] = pow(i * (i + 1) / 2, 2) - s2[i];
r3[i] = pow(i * (i + 1) / 2, 3) - s3[i];
r4[i] = pow(i * (i + 1) / 2, 4) - s4[i];
++i;
}

int nN;
while (scanf(";%d";, nN) != EOF)
{
//printf(";%I64u %I64u %I64u %I64u %I64u %I64u\n";, s2[nN], r2[nN], s3[nN], r3[nN], s4[nN], r4[nN]);
printf(";%llu %llu %llu %llu %llu %llu\n";, s2[nN], r2[nN], s3[nN], r3[nN], s4[nN], r4[nN]);
}

return 0;
}