Sum of Tribonacci Numbers 要如何实现

Question

Problem Description
Everybody knows Fibonacci numbers, now we are talking about the Tribonacci numbers:
T[0] = T[1] = T[2] = 1;
T[n] = T[n - 1] + T[n - 2] + Tn - 3

Given a and b, you are asked to calculate the sum from the ath Fibonacci number to the bth Fibonacci number, mod 1,000,000,007, that is (T[a] + T[a + 1] + ... + T[b]) % 1,000,000,007.

Input
There are multiple cases (no more than 100).

Each case contain two non-negative integers a b(a <= b and a, b < 1,000,000,000)

Output
For each case, output the sum % 1,000,000,007.

Sample Input
0 2
0 5

Sample Output
3
20

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# 二分法查找递归求和时间复杂度O(n^2)
# 较为简单直接的实现思路是使用动态规划方法求解
# 动态规划的求和方式可以看作是一个二进制加法问题，即：
# T[i] = T[i-1] + T[i-2] + T[i-3]
# 题目要求从T[a]到T[b]（含）的累加和，即T[a] + T[a+1] + ... + T[b]
# 所以我们可以将问题转化为求T[a]...T[b]在二进制中的第几位
# 即求和的位数，然后对每一位进行模运算即可
# 这里我们用哈希表记录每个数字出现的位置，利用前缀和的方法计算出答案

fib = function(x){
  if(x==0) return(1)
  if(x==1) return(1)
  if(x==2) return(1)
  res = c(1, 1, 1)
  for(i in 3:x){
    res = c(res[res[-1]+res[-2]+res[-3]], res)
  }
  res
}

tri = function(a,b){
  s = fib(b-a+1)
  x = s[which(s == min(s))]
  y = which(s == max(s))
  if(y[1]<a || y[1]>b) return(-1)
  if(x<y[1]) return(-1)
  z = x-y[1]+1
  t = ((b-a+1)*z)/2
  if(t%2 != 0) return((t/2)%1e9+1)
  (t/2)
}