一些技巧

求多个数最大值：

max({......});

转换成滚动数组

将数组第一维改为2，在每次循环开始前清空下数组，每个第一维都与上一个1。

修改后

int f[2][4];

for (int i = 1; i <= n; i ++ )
{
    memset(f[i + 1 & 1], 0, sizeof f[0]);
    for (int j = 0; j < 4; j ++ )
        for (int k = 0; k < 4; k ++ )
            f[i + 1 & 1][k] = (f[i + 1 & 1][k] + f[i & 1][j] * g[j][k]) % MOD;
}

printf("%d\n", f[n + 1 & 1][0]);

修改前

int f[N][4];

for (int i = 1; i <= n; i ++ )
{
    for (int j = 0; j < 4; j ++ )
        for (int k = 0; k < 4; k ++ )
            f[i + 1][k] = (f[i + 1][k] + f[i][j] * g[j][k]) % MOD;
}

printf("%d\n", f[n + 1 & 1][0]);

减小常数

尽量将乘法改成加法。