题目链接 https://nanti.jisuanke.com/t/38222
题意：
定义函数：
$$F(n)=\left\{
\begin{aligned}
1, \quad n=1,2 \\
F(n-1)+F(n-2),\quad n\geq3 \quad
\end{aligned}
\right.
$$
给定一个W 找到一个字典序最小的集合S使得
$$W=\sum_{f\in S}F(F(f))$$
$1\leq T\leq 10$
$1\leq W\leq 10^{100,000}$
解析：java大数打表可以发现 当f >28时已经超过W上界了，所以快速幂求出来前28项就好了，数增加的非常快，只有当W<=10时才有 多个解的情况
所以从大的开始减，当减到第五项的时候 再分类讨论一下就好了。
AC代码
import java.util.*;
import java.math.*; public class Main { static class Matrix {
public static int maxn = ;
BigInteger a[][] = new BigInteger [maxn][maxn];
public void init() {
for (int i = ; i < maxn; ++i) for (int j = ; j < maxn; ++j) a[i][j] = BigInteger.ZERO;
}
public void _init() {
init();
for (int i = ; i < maxn; ++i) a[i][i] = BigInteger.ONE;
}
public static Matrix mul(Matrix A, Matrix B) {
Matrix res = new Matrix();
res.init();
for (int i = ; i < maxn; ++i) {
for (int j = ; j < maxn; ++j) {
for (int k = ; k < maxn; ++k) {
res.a[i][k] = res.a[i][k].add(A.a[i][j].multiply(B.a[j][k]));
}
}
}
return res;
}
public static Matrix q_pow(Matrix A, BigInteger k) {
Matrix res = new Matrix();
res._init();
while(k.compareTo(BigInteger.ZERO) > ) {
if(k.mod(BigInteger.valueOf()).compareTo(BigInteger.ZERO) > ) res = mul(res, A);
A = mul(A, A);
k = k.shiftRight();
}
return res;
}
}
public static BigInteger get_fib(BigInteger n) {
if(n.compareTo(BigInteger.ONE) == ) return BigInteger.ONE;
if(n.compareTo(BigInteger.valueOf()) == ) return BigInteger.ONE;
Matrix A = new Matrix();
A.a[][] = BigInteger.ZERO;
A.a[][] = A.a[][] = A.a[][] = BigInteger.ONE;
A = Matrix.q_pow(A, n.subtract(BigInteger.valueOf()));
return A.a[][].add(A.a[][]);
} public static void main(String[] args) { BigInteger f[] = new BigInteger[];
int ans[] = new int[];
Scanner cin = new Scanner(System.in);
int T = cin.nextInt();
for (int i = ; i <= ; ++i) {
f[i] = Main.get_fib(Main.get_fib(BigInteger.valueOf(i)));
}
while(T--> ) {
BigInteger W = cin.nextBigInteger();
int cnt = ;
for (int i = ; i >= ; --i) {
if(f[i].compareTo(W) <= ) {
ans[++cnt] = i;
W = W.subtract(f[i]);
}
}
if(W.compareTo(BigInteger.valueOf()) == ) {
ans[++cnt] = ;
}
else if(W.compareTo(BigInteger.valueOf()) == ){
ans[++cnt] = ;
ans[++cnt] = ;
}
else if(W.compareTo(BigInteger.valueOf()) == ) {
ans[++cnt] = ;
ans[++cnt] = ;
ans[++cnt] = ;
}
else if(W.compareTo(BigInteger.valueOf()) == ) {
ans[++cnt] = ;
ans[++cnt] = ;
ans[++cnt] = ;
}
else if(W.compareTo(BigInteger.valueOf()) == ) {
ans[++cnt] = ;
ans[++cnt] = ;
ans[++cnt] = ;
ans[++cnt] = ;
}
else if(W.compareTo(BigInteger.valueOf()) == ) {
ans[++cnt] = ;
ans[++cnt] = ;
}
else if(W.compareTo(BigInteger.valueOf()) == ) {
ans[++cnt] = ;
ans[++cnt] = ;
ans[++cnt] = ;
}
else if(W.compareTo(BigInteger.valueOf()) == ) {
ans[++cnt] = ;
ans[++cnt] = ;
ans[++cnt] = ;
ans[++cnt] = ;
}
else if(W.compareTo(BigInteger.valueOf()) == ) {
ans[++cnt] = ;
ans[++cnt] = ;
ans[++cnt] = ;
ans[++cnt] = ;
}
else if(W.compareTo(BigInteger.valueOf()) == ) {
ans[++cnt] = ;
ans[++cnt] = ;
ans[++cnt] = ;
ans[++cnt] = ;
ans[++cnt] = ;
}
else if(W.compareTo(BigInteger.ZERO)!=){
System.out.println(-);
continue;
}
for (int i = cnt; i >= ; --i) {
if(i == )
System.out.println(ans[i]);
else
System.out.print(ans[i]+" ");
}
}
} }