$$\begin{bmatrix} 1 & 5 & 1 & -1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 \end{bmatrix} *\begin{bmatrix} f(x-1) \\ f(x-2) \\ f(x-3) \\ f(x-4) \end{bmatrix}=\begin{bmatrix} f(x) \\ f(x-1) \\ f(x-2) \\ f(x-3) \end{bmatrix}$$ $$A^{n-4}* \begin{bmatrix} f(4)=36 \\ f(3)=11 \\ f(2)=5 \\ f(1)=1 \end{bmatrix}= \begin{bmatrix} f(x) \\ f(x-1) \\ f(x-2) \\ f(x-3) \end{bmatrix}$$ $f(x)=A[0][1]*f(4)+f[0][1]*f(3)+f[0][2]*f(2)+f[0][3]*f(4)$

# 题意

$f(x)=f(x-1)+f(x-2) \ , (f(0)=0,f(1)=f(2)=1)$
• 如果$n$ 为奇数$f(n)=(f(n-1)+f(n-2)) \ xor \ 1$
$if(c=a+b为奇数) \ c \ xor \ 1=c-1;$ $else \ c=c+1$
• 如果$n$ 为偶数$f(n)=(f(n-1)+f(n-2)) \ xor \ 0$

$f(x)$

# 思路

$w(x)=\frac{ Fi(x)-g(x)}{2}=a_x-a_{x-1}$ $g(x)=0 \ ，if(n是6的倍数)$ $g(x)=-1，if(n-1是6的倍数)$ $g(x)=-2，if(n是3的倍数且\frac{n}{3}为奇数)$ $g(x)=1，if(其余情况)$

$\displaystyle \sum_{i=1}^{k} g(x) = (-k+(\frac{k}{6}+(\frac{k-1}{6}+1) \times 2+\frac{ k/3+1 } {2} *3)$
$\displaystyle a_n=(\sum_{i=2}^{n}w(i) \ ) +1$
$\displaystyle \sum_{i=2}^{n}w(i)=(\sum_{i=1}^{n}w(i))\ -1$
$\displaystyle a_n=\sum_{i=1}^{n}w(i)=\frac{\sum_{i=1}^{n}Fi(i) \ -\sum_{i=1}^{n}g(i)}{2}=\frac{Fi(n+2)-1-\sum_{i=1}^{n}g(i)}{2}$

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63  #include using namespace std; typedef unsigned long long ll; const ll mod = 1000000007; //2对于mod的逆元为 500000004 const ll inv2 = 500000004; struct Matrix { ll v[2][2]; Matrix() { memset(v, 0, sizeof(v)); } Matrix operator * (const Matrix y) { Matrix ans; for(int i = 0; i <= 1; i++) for(int j = 0; j <= 1; j++) for(int k = 0; k <= 1; k++) ans.v[i][j] += v[i][k]y.v[k][j]; for(int i = 0; i <= 1; i++) for(int j = 0; j <= 1; j++) ans.v[i][j] = ans.v[i][j]%mod; return ans; } void operator = (const Matrix b) { for(int i = 0; i <= 1; i++) for(int j = 0; j <= 1; j++) v[i][j] = b.v[i][j]; } }; ll solve(ll x) { Matrix ans, trs; ans.v[0][0] = ans.v[1][1] = 1; trs.v[0][0] = trs.v[1][0] = trs.v[0][1] = 1; while(x) { if(x&1) ans = anstrs; trs = trstrs; x >>= 1; } return ans.v[0][0]; } int GX[]={0,1,0,2,1,0,0}; int main() { ll k; int t;scanf("%d",&t); while(t--) { //freopen("C:\Users\gavin\Desktop\AC.txt","r",stdin); //freopen("C:\Users\gavin\Desktop\WA.txt","w",stdout); scanf("%lld",&k); if(k==1) {printf("1\n");continue;} if(k==2) {printf("1\n");continue;} if(k==3) {printf("3\n");continue;} ll IN = k+2; ll fi_n = solve(IN-1); /* cout<<" 0="<

## python 打表代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  list = [] for i in range(10000): list.append([]) list[0] = 0 list[1] = 1 list[2] = 1 list[3] = 2 mod = 1000000007 for i in range(3, 1001): if i % 2 == 1: list[i] = (list[i - 1] + list[i - 2]) ^ 1 if i % 2 == 0: list[i] = (list[i - 1] + list[i - 2]) ^ 0 # for i in range(3,101): # list[i] = list[i-1] + list[i-2] # 斐波那契数列 for i in range(1,1001): print(list[i] % mod)

## Java 代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61  import java.io.BufferedInputStream; import java.io.IOException; import java.math.BigInteger; import java.util.Scanner; import java.util.Vector; public class Main { public static long mod = 1000000007; public static long inv2= 500000004; public static int GX[]={0,1,0,2,1,0,0}; public static long muti(long a, long b) { if (a >= mod) a %= mod; if (b >= mod) b %= mod; return (a * b) % mod; } public static long[][] matrixf(long[][] mat1, long[][] mat2) { long[][] T = new long[2][2]; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) T[i][j] = T[i][j] + muti(mat1[i][k], mat2[k][j]); return T; } public static long power_mod(BigInteger n) { long ans[][] = new long[2][2], trs[][] = new long[2][2]; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) ans[i][j] = trs[i][j] = 0; for (int i = 0; i < 2; i++) ans[i][i] = 1; trs[0][0] = trs[1][0] = trs[0][1] = 1; trs[1][1] = 0; while (n.compareTo(BigInteger.valueOf(0)) > 0) { if (n.mod(BigInteger.valueOf(2)).compareTo(BigInteger.valueOf(1)) == 0) ans = matrixf(ans, trs); trs = matrixf(trs, trs); n = n.divide(BigInteger.valueOf(2)); } return ans[0][0]; } private static Scanner cin; public static void main(String[] args) throws IOException { cin = new Scanner(new BufferedInputStream(System.in)); int T = cin.nextInt(); for (int cnt = 1; cnt <= T; cnt++){ BigInteger n = cin.nextBigInteger(), one = new BigInteger("1"); if (n.compareTo(BigInteger.valueOf(1)) == 0) { System.out.println("1");continue; } if (n.compareTo(BigInteger.valueOf(2)) == 0) { System.out.println("1");continue; } if (n.compareTo(BigInteger.valueOf(3)) == 0) { System.out.println("3");continue; } if (n.compareTo(BigInteger.valueOf(4)) == 0){ System.out.println("4");continue; } long gx = GX[n.mod(BigInteger.valueOf(6)).intValue()]; long sum = (power_mod(n.add(one)) -1 + gx)%mod; System.out.println(sum * inv2 % mod); } } }