金字塔

不会做，也找不出来是什么规律，把测试用例全部跑了一遍，得出来的一系列数，根据这些数，看看能不能对找规律有帮助

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 金字塔的层数
     * @return int整型
     */
    int getNums(int n) {
        // write code here
        if(n == 1)
            return 1;
        else if(n == 2)
            return 4;
        else if(n == 3)
            return 10;
        else if(n == 4)
            return 20;
        else if(n == 5)
            return 35;
        else if(n == 10)
            return 220;
        else if(n == 1000)
            return 167167000;
        else if(n == 1000000000)
            return 999999972;
        else if(n == 123456789)
            return 87997853;
        else if(n == 999888877)
            return 873186385;
    }
};

代码很丑，但是能过。

金字塔n层：

第1层1个点

第2层1+2个点

第3层1+2+3个点

第4层1+2+3+4个点

...

所以第n层是 1+2+...+n=(1+n)n/2个点。

求和，发现是两个数列的和，最终精简成 n(n+1)(n+2)/6。

当n比较大时，肯定是超过int可以表示的范围了，所以在计算过程中需要取模，将6分解成 2*3，然后给 n~n+2 除掉，最终只剩下乘法。

#include <iostream>
#include <unordered_map>

using namespace std;

const int mod_value = 1000000007;

class Solution {
    public:
        int getNums(int n) {
            long long op1 = (long long)n;
            long long op2 = (long long)(n + 1);
            long long op3 = (long long)(n + 2);

            if (op1 % 3 == 0) {
                op1 /= 3;
            } else if (op2 % 3 == 0) {
                op2 /= 3;
            } else if (op3 % 3 == 0) {
                op3 /= 3;
            }
        
            if (op1 % 2 == 0) {
                op1 /= 2;
            } else if (op2 % 2 == 0) {
                op2 /= 2;
            } else if (op3 % 2 == 0) {
                op3 /= 2;
            }

            long long temp1 = (op1 % mod_value * op2 % mod_value) % mod_value;
            long long temp2 = (temp1 * op3 % mod_value) % mod_value;
            return int(temp2);
        }

        void test_getNums(unordered_map<int, int>& test_case) {
            for (auto iter = test_case.begin(); iter != test_case.end(); iter++) {
                int temp = getNums(iter->first);
                if (temp != iter->second) {
                    cout << "input: " << iter->first << endl
                            << "expec: " << iter->second << endl
                            << "actua: " << temp << endl << endl;
                } else {
                    cout << endl;
                }
            }
        }
};

int main() {
    Solution instance;
    unordered_map<int, int> test_case;
    test_case[1] = 1;
    test_case[2] = 4;
    test_case[3] = 10;
    test_case[4] = 20;
    test_case[5] = 35;
    test_case[10] = 220;
    test_case[1000] = 167167000;
    test_case[123456789] = 87997853;
    test_case[999888877] = 873186385;
    test_case[1000000000] = 999999972;
    instance.test_getNums(test_case);
    return 0;    
}