hdu 1220Cube<数学题>

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1220

题意：一个正方体，切割成单位体积的小正方体，求所有公共顶点数<=2的小正方体的对数；

思路：

对于正方体中的任意两个单位正方体，其公共顶点数为 0， 2， 4；

由容斥原理可知，只要减去公共顶点为4的即可。故答案为 $\binom{n^{3}}{2}-3n^{2}(n-1)$ 种。

首先总共有 n^3 个立方体从中选2个，其次只有相邻的立方体才是4，所以每一列有n-1对，每个面有n^2列，前后，左右，上下是一样的共三个方向；

View Code

1 #include <cstdio>
2 int main( )
3 {
4     int N;
5     while( scanf( "%d", &N )==1 ){
6         printf( "%d\n", N*N*N*(N*N*N-1)/2-3*N*N*(N-1) );
7     }
8     return 0;
9 }