南昌网络赛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\{
\begin{aligned}
1,&&n = 1,2 \\
F(n-1)+F(n-2), && n\ge3
\end{aligned}
\right.
\]

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

They calculated the value of $W=\sum_{f\in 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

$1\le T \le10 $

$1\le W \leq 10^{100,000}$

样例输入

样例输出

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;

	}

}

巴特西

南昌网络赛C.Angry FFF Party

南昌网络赛C.Angry FFF Party

Describe

Input

Output

Constraints

样例输入

样例输出

题意

题解

n天之后新发现：

代码

最新文章

热门文章