Tribonacci(泰波那契)数列前n项和的求解问题

 
Tribonacci数列是斐波那挈数列的扩展

 
很有趣的，我们可以发现 

这是Tribonacci数列的一些深入研究 
下面是贴代码的时间了： 
解法一（半产品） 
这种方法就不解释了，不懂就去看看最笨的方法递归求解，而这是对递归求解的优化

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNext()) {

            long l = scanner.nextLong();
            long r = scanner.nextLong();
            long sum = 0;
             sum = sum_tribonacci(l, r);
             System.out.println(sum % 1000000007);
//          for (long i = 0; i <= 100l; i++) {
//              sum = sum_tribonacci(0, i);
//              System.out.println(i + "---------------------------" + sum
//                      % 1000000007l);
//          }

        }
    }

    public static long sum_tribonacci(long l, long r) {
        long n1 = 0, n2 = 0, n3 = 0;
        long u1, u2;
        long sum = 0;
        if (r < 3) {
            return (r - l + 1);
        }

        n1 = 0;
        n2 = 1;
        n3 = 2;
        // n1 = 1;
        // n2 = 1;
        // n3 = 1;
        long n4 = 0;
        if (l < 3) {
            // for (long i = 3; i <= r; i++) {
            for (long i = 3; i <= r + 1; i++) {
                n4 = n3 + n2 + n1;
                n1 = n2;
                n2 = n3;
                n3 = n4;
            }
            sum = n3 - l;
            return sum;

        } else {
            // for (long i = 3; i <= l; i++) {
            for (long i = 3; i <= l; i++) {
                n4 = n3 + n2 + n1;
                n1 = n2;
                n2 = n3;
                n3 = n4;
            }
            long sum1 = n3;
            // sum+=n4;
            for (long i = l + 1; i <= r + 1; i++) {
                n4 = n3 + n2 + n1;
                n1 = n2;
                n2 = n3;
                n3 = n4;
            }
            long sum2 = n3;
            return sum2 - sum1;
        }
    }

}

 

解法二 
 
所以这里关键是要求出矩阵A 
可以用前5项求出矩阵（数列{1、2、3、6、11…}依题意这是数列{1、1、1、3、5…}前n-1项的和，依然满足Tribonacci规则） 
这里矩阵的n次幂，我采用的是二分法。

  1 import java.math.BigDecimal;
  2 import java.util.Scanner;
  3 
  4 public class CopyOfMain2 {
  5     public static BigDecimal i1000000007 = new BigDecimal(
  6             String.valueOf(1000000007));
  7     //这里定义了四个数，其实是为了下面BigDecimal数组的初始化做准备
  8     public static BigDecimal i3 = new BigDecimal(String.valueOf(3));
  9     public static BigDecimal i2 = new BigDecimal(String.valueOf(2));
 10     public static BigDecimal i1 = new BigDecimal(String.valueOf(1));
 11     public static BigDecimal i0 = new BigDecimal(String.valueOf(0));
 12 
 13     public static void main(String[] args) {
 14         Scanner scanner = new Scanner(System.in);
 15 
 16         while (scanner.hasNext()) {
 17 
 18             long l = scanner.nextLong();
 19             long r = scanner.nextLong();
 20             BigDecimal[] sum = {i0,i0};
 21 
 22 
 23             sum = Tribonacci(l, r).divideAndRemainder(i1000000007);
 24             if(sum[1].longValue()<0)System.out.println(sum[1].add(i1000000007));
 25             else System.out.println(sum[1]);
 26             //这是比较笨的方法，用这种遍历的求和方式当然会超时
 27             // for (long i = l; i <= r; i++) {
 28             //    sum += Tribonacci(i);
 29             // }
 30             // for(long i =0; i <= 100l; i++){
 31             //    sum=Tribonacci(0,i);
 32             //    System.out.println(i+"---------------------------"+sum %
 33             //    1000000007l);
 34             // }
 35         }
 36     }
 37 
 38     public static BigDecimal Tribonacci(long l, long r) {
 39         BigDecimal sum = i0;
 40         if (r < 3) {
 41             for (long i = l; i <= r; i++) {
 42                 sum = new BigDecimal(String.valueOf(r - l + 1));
 43             }
 44             return sum;
 45         }
 46         BigDecimal[][] base = { { i1, i1, i0 }, { i1, i0, i1 }, { i1, i0, i0 } };
 47         if (l >= 3l) {
 48             BigDecimal[][] res1 = matrixPower(base, l - 3);
 49 
 50             BigDecimal[][] res = matrixPower(base, r - 2);
 51             // long[][] res = muliMatrix(res1,matrixPower(base, r- l+1));
 52             return (res[0][0].subtract(res1[0][0])).multiply(i3)
 53                     .add((res[1][0].subtract(res1[1][0])).multiply(i2))
 54                     .add((res[2][0].subtract(res1[2][0])));
 55         } else {
 56             BigDecimal[][] res = matrixPower(base, r - 2);
 57             return (res[0][0].multiply(i3).add(res[1][0].multiply(i2))
 58                     .add(res[2][0]).subtract(new BigDecimal(String.valueOf(l))));
 59         }
 60 
 61     }
 62     //求Tribonacci数列每一项的方法
 63     // public static long Tribonacci(long n) {
 64     // if (n == 0l || n == 1l || n == 2l) {
 65     // return 1;
 66     // } else if (n == 3l)
 67     // return 3;
 68     // long[][] base = { { 1l, 1l, 0l}, { 1l, 0l, 1l }, { 1l, 0l, 0l } };
 69     // long sum = 0l;
 70     //
 71     // long[][] res = matrixPower(base, n - 3l);
 72     //
 73     // return 3l * res[0][0] + res[1][0] + res[2][0];
 74     // }
 75 
 76     public static BigDecimal[][] matrixPower(BigDecimal[][] base, long p) {
 77         BigDecimal[][] res = new BigDecimal[base.length][base[0].length];
 78         for (int i = 0; i < res.length; i++) {
 79             for (int j = 0; j< res[0].length; j++) {
 80                 if (i == j) {
 81                     res[i][j] = i1;
 82                 } else
 83                     res[i][j] = i0;
 84             }
 85 
 86         }
 87         BigDecimal tmp[][] = base;
 88         for (; p != 0; p >>= 1) {
 89             if ((p & 1) != 0) {
 90                 res = muliMatrix(res, tmp);
 91             }
 92             tmp = muliMatrix(tmp, tmp);
 93         }
 94         return res;
 95     }
 96 
 97     private static BigDecimal[][] muliMatrix(BigDecimal[][] m1,
 98             BigDecimal[][] m2) {
 99         BigDecimal[][] res = new BigDecimal[m1.length][m2[0].length];
100         for (int i = 0; i < res.length; i++) {
101             for (int j = 0; j< res[0].length; j++) {
102                 res[i][j] = i0;
103             }
104         }
105         for (int i = 0; i < m1.length; i++) {
106             for (int j = 0; j < m2[0].length; j++) {
107                 for (int k = 0; k < m2.length; k++) {
108 
109                         res[i][j] = res[i][j].add(m1[i][k].multiply(m2[k][j])).divideAndRemainder(i1000000007)[1];
110 
111                 }
112             }
113         }
114         return res;
115 
116     }
117 
118 }