已知:
对于任意(i−1)(i-1) % 4 != 0(i−1)有:
fi=fi−1+fi−4f_{i} = f_{i-1} + f_{i-4}fi=fi−1+fi−4
对于任意(i−1)(i-1) % 4 =0(i−1)有:
fi=fi−1+fi−5f_{i} = f_{i-1} + f_{i-5}fi=fi−1+fi−5
特殊的,f1,f2,f3,f4,f5f_1, f_2, f_3, f_4, f_5f1,f2,f3,f4,f5题目将给出
求fnf_nfn,保证n%4为0,n<=10910^9109
O(n)被出题人卡了,感觉可以矩阵?但我构造不出