斐波那契变形：树形开路

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        long g = 10000000007L;
        int n = sc.nextInt();
        long a[] = new long[n + 1];
        a[1] = 1;a[2] = 2;long sum = 3;
        if(n == 1){
            System.out.println(1);
            return;
        }else if(n == 2){
            System.out.println(3);
            return;
        }
        for(int i = 3;i <= n;i++){
            a[i] = (a[i-1]+a[i-2])%g;
            sum = (sum + a[i]) % g;
        }
        System.out.println(sum);

    }
}

做题要画出一个树形图，第一天只能打通一条路，总共道路sum=1，第二天有两个节点，就可以分工，可以多打两条道路，那么总共的sum就是之前的1+2条。那么每天打通的道路就形成一个斐波那契数列，只需要把每天打通的道路加上之前的sum就能得到总共的sum（自己想得太复杂了）。最后一个就是数据溢出，学到了一个新东西，因为数据量比较大，要注意在计算的过程中，是否会有数据溢出，所以要对每一步的计算结果取模就行。保证数据不溢出。