2025/03/16蚂蚁笔试第三题思路和代码

思路：仔细数出n<=5的情况总数。分别为1 4 12 28 60，其中12=(1+2+1) * 4 - 4，28=(1+3+3+1) * 4-4, 60=(1+4+6+4+1) * 4-4

可以发现规律：答案和杨辉三角有关。得到公式res=2^(n+1)-4，快速幂计算即可。

#include <bits/stdc++.h>
using namespace std;
const long mod = 1e9 + 7;
long qsm(long a, long b) {
    long res = 1;
    while (b > 0) {
        if (b % 2 == 1) res = res * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return res;
}
int main() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }
    long res = qsm(2, n + 1);
    res = (res - 4 + mod) % mod;
    cout << res << endl;
    return 0;
}

蚂