小编You*_*IAm的帖子

该问题的时间复杂度不同于所提出的类似问题。这是Zauba开发人员招聘挑战（活动在一个月前结束）的一个问题：

f(0) = p
f(1) = q
f(2) = r

for n > 2

f(n) = a*f(n-1) + b*f(n-2) + c*f(n-3) + g(n)

where g(n) = n*n*(n+1)

p, q, r, a, b, c, n给出。n可以和一样大10^18。

链接到类似问题

在上面的链接中，没有指定时间复杂度，并且我已经在中解决了此问题O(n)，伪代码在下面（只是一种方法，所有可能的边界和边缘情况都在比赛中处理）。

if(n == 0) return p;
if(n == 1) return q;
if(n == 2) return r;
for(long i=3;i<=n;i++){
    now = a*r + b*q + c*p + i*i*(i+1);
    p = q; q = r; r = now;
}

请注意，我 …