#### 备忘：

$$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)$

## 异或+矩阵快速幂(excel+python打表法)

$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$ 打表可轻松得 $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}$ #include <bits/stdc++.h> 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]<em>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 = ans</em>trs; trs = trs<em>trs; 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="<<k/6<<endl;
cout<<" 1="<<k<<endl;
cout<<"-1="<<(k-1)/6+1<<endl;
cout<<"-2="<<(k/3+1)/2<<endl;
*/
//ll gx = (-k+(k/6+((k-1)/6+1)</em>2+(k/3+1)/2*3)+mod)%mod;
ll gx2 = GX[k%6];
//printf("%lld : %d$n",k,gx); ll ret = (fi_n-1+gx2)%mod; printf("%lld$n",(ret*inv2%mod));
}
}

##### python 打表代码
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)


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);
}
}
}


This site uses Akismet to reduce spam. Learn how your comment data is processed.