南昌网络赛C.Angry FFF Party

Describe

In ACM labs, there are only few members who have girlfriends. And these people can make FFF Party angry easily. One day, FFF Party prepared a function (F)and a set (S).

[left{ egin{aligned} 1,&&n = 1,2 \ F(n-1)+F(n-2), && nge3 end{aligned} ight. ]

There are several unequal positive integers $ f _i$ in the set (S).

They calculated the value of (W=sum_{fin s}{F(F(f))}), and tried to cause (W)damage to those who have girlfriends. Suppose you are not a single dog and have been attacked. Now, give you the value of (W) and please write a program to calculate these (fi) in set (S).

Input

The first line consists of a single integer (T) denoting the number of test cases.

(T) lines follow, with an integer in each, denoting the result of (W).

Output

For each test case, print a sequence of space-separated integers (fi) satisfying the equation.

If there are more than one answers, please print the lexicographically smallest one.

If there’s no such sequence, print (-1) instead.

Constraints

$1le T le10 $

(1le W leq 10^{100,000})

样例输入

2
1
3

样例输出

1
1 2 3

题意

给你一个很大的数，让你从斐波拉切的斐波拉切数列中选择任意多个数，使其和等于这个数。

题解

本来想直接复制粘贴题目的，但是数学公式实在太恶心，复制不过来，于是就按照(OYJY)大佬的指示，下载了个markdown编辑器typora ,但是不知是我的linux系统不行，还是搜狗输入法不行，切换不了中文输入法，于是悲催的我只能再wps中打中文，再粘贴过去。qwq.

n天之后新发现：

原来只要不从终端打开typora就可以切换输入法啦。另外告诉各位不能显示数学公式的小伙伴，在新建随便的那个页面左栏设置默认编辑器里，需要勾选启用数学公式支持

开始进入正题，通过打表 ~~c++已选手退出群聊~~ 发现，其实只有28个数，而且除了前五个数相差较小，后面的数基本相差巨大，也就是前面所有的数加起来都没有下一个数大。于是我们从大到小一个一个减，能减就减，到零或者剪完为止，是不是很简单,。

但是我不会 java ,于是我学了一天的 java,安装eclipse安了一下午，~~菜的真实~~，然后刷了几道水题，最终切了这道早就想切的题了。

因为输入的是字典序最小的一组解，所以当数小与(10)时，要打表处理

代码

import java.io.*;
import java.math.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) 
	{
		Scanner cin=new Scanner(new BufferedInputStream(System.in));
		
		BigInteger list[]=new BigInteger[30];
		BigInteger tp[][]=new BigInteger[3][3],a[][]=new BigInteger[3][3];
		int f[]=new int[30],flag=0;
		a[1][1]=BigInteger.ONE; a[1][2]=BigInteger.ONE;
		a[2][1]=BigInteger.ONE; a[2][2]=BigInteger.ZERO;
		f[0]=0; f[1]=1;
		
		for(int i=2;i<=29;i++) f[i]=f[i-1]+f[i-2];
		for(int i=1;i<=29;i++)
		{
			tp=MatrixPower(a,2,f[i]-1);
			list[i]=tp[1][1];
		}
		//for(int i=1;i<=20;i++) System.out.println(list[i]);
		int tot=0; tot=cin.nextInt();
		while(tot>0)
		{
			tot=tot-1;
			BigInteger n=cin.nextBigInteger();
			//tp=MatrixPower(a,2,n-1);
			//System.out.println(tp[1][1].toString());
			flag=get_ans(n,28,list);
			if (tot>0)System.out.println("");
		}
	}
	public static int get_ans(BigInteger n,int maxn,BigInteger list[])
	{
		//System.out.println("now= "+n);
		if (n.compareTo(BigInteger.ZERO)==0) return 0;
		if (maxn==0||maxn==4)
		{
			System.out.print("-1");
			return -1 ;
		}
		BigInteger a[]=new BigInteger[11];
		for(int i=1;i<=10;i++) a[i]=BigInteger.valueOf(i);
		if (n.compareTo(a[10])<=0)
		{
			//System.out.println("lalala ");
			if (n.compareTo(a[1])==0)System.out.print("1");
			if (n.compareTo(a[2])==0)System.out.print("1 2");
			if (n.compareTo(a[3])==0)System.out.print("1 2 3");
			if (n.compareTo(a[4])==0)System.out.print("1 2 4");
			if (n.compareTo(a[5])==0)System.out.print("1 2 3 4");
			if (n.compareTo(a[6])==0)System.out.print("1 5");
			if (n.compareTo(a[7])==0)System.out.print("1 2 5");
			if (n.compareTo(a[8])==0)System.out.print("1 2 3 5");
			if (n.compareTo(a[9])==0)System.out.print("1 2 4 5");
			if (n.compareTo(a[10])==0)System.out.print("1 2 3 4 5");
			return 0;
		}
		for(int i=maxn;i>=1;i--)
		{
			if (n.compareTo(list[i])>=0)
			{
				BigInteger tt=n.subtract(list[i]);
				int pd=get_ans(n.subtract(list[i]),i-1,list);
				if (pd==0 && tt.compareTo(BigInteger.ZERO)>0)System.out.printf(" ");
				if (pd==0)System.out.printf("%d",i);
				if (pd==0)return 0;
				return -1;
			}
		}
		return 0;
	}
	public static BigInteger[][] MatrixMultiply(BigInteger a[][],BigInteger b[][],int n,int p,int m)
	{
		BigInteger c[][]=new BigInteger[n+1][m+1];
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			c[i][j]=BigInteger.ZERO;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)	
		for(int k=1;k<=p;k++)
			c[i][j]=c[i][j].add(a[i][k].multiply(b[k][j]));
		return c;
	}
	public static BigInteger[][] MatrixPower(BigInteger a[][],int n,int p)
	{
		BigInteger ans[][]=new BigInteger[n+1][n+1];
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if (i==j)ans[i][j]=BigInteger.ONE;
			else ans[i][j]=BigInteger.ZERO;
		while(p>0)
		{					 
			if ((p&1)==1)ans=MatrixMultiply(ans,a,n,n,n);
			p=p/2;
			a=MatrixMultiply(a,a,n,n,n);
		}
		return ans;
	}
}