-4

给定一个正四面体。所有的边被分成N个相等的段。在这个四面体内部可以构建多少个顶点在分割点的非退化（|volume|>0）四面体？给定四面体的顶点不能作为分割点。

例子：

  • 对于 N=2，答案是 12。
  • 对于 N=37，答案是 65561472。

这是一些伪代码的答案，但我未能将最后一步翻译成 C++。这是我到目前为止所做的：

typedef unsigned long long ulong;
ulong histogram[3002];

int main() {
    memset(&histogram[0],0,sizeof(ulong)*3002);
    ulong N;
    cin >> N;
    ulong m = N-1;
    ulong u,U,z,Z;
    ulong tetra = 3*m*m*(53*m*m-34*m+1)/4;

    for( u = 1; u < N; u++) {
        U = u/(N-u);
        for( z = 1; z < N; z++) {
            Z = z/(N-z);
            histogram[U*Z]++;
        }
    }

    // How to write the following steps in C++?
    /*number_degen = 0;
    foreach fraction in histogram {
        number_degen += histogram{fraction}^2;
    }*/
    // I am trying something like this
    ulong number_degen = 0;
    for (int i = 0; i<3002; i++)
        number_degen += histogram[i] * histogram[i];


    cout<<number_degen<<endl;
    cout<<tetra-3*number_degen<<endl;
}

"number_degen" = "950404" 如果 N=37，当它必须是 4836 时

4

1 回答 1

2

一个问题（它可能是您的实现中唯一缺少的）是您如何在 C++（和许多其他语言）中取正方形：

number_degen += histogram[fraction] ^ 2;    // <-- wrong!

^C++ 中的运算符不会计算两个数字的幂，而是它们的按位 XOR 组合。要取两个数字的平方，有两种可能：要么将数字与自身相乘，要么取其为 2 的幂。对于整数，应该首选第一个，因为采用数字的幂将产生浮点数。

number_degen += histogram[fraction] * histogram[fraction];
于 2013-02-18T16:41:00.593 回答