首页 > 其他 > 详细

2019南昌邀请赛 C. Angry FFF Party 大数矩阵快速幂+分类讨论

时间:2019-04-21 21:28:06      阅读:217      评论:0      收藏:0      [点我收藏+]

题目链接 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 = 2;
        BigInteger a[][] = new BigInteger [maxn][maxn];
        public void init() {
            for (int i = 0; i < maxn; ++i) for (int j = 0; j < maxn; ++j) a[i][j] = BigInteger.ZERO;
        }
        public void _init() {
            init();
            for (int i = 0; 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 = 0; i < maxn; ++i) {
                for (int j = 0; j < maxn; ++j) {
                    for (int k = 0; 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) > 0) {
                if(k.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO) > 0) res = mul(res, A);
                A = mul(A, A);
                k = k.shiftRight(1);
            }
            return res;
        }
    }
    public static BigInteger get_fib(BigInteger n) {
        if(n.compareTo(BigInteger.ONE) == 0) return BigInteger.ONE;
        if(n.compareTo(BigInteger.valueOf(2)) == 0) return BigInteger.ONE;
        Matrix A = new Matrix();
        A.a[1][1] = BigInteger.ZERO;
        A.a[0][0] = A.a[1][0] = A.a[0][1] = BigInteger.ONE;
        A = Matrix.q_pow(A, n.subtract(BigInteger.valueOf(2)));
        return A.a[0][0].add(A.a[0][1]);
    }

    public static void main(String[] args) {
        
        BigInteger f[] = new BigInteger[100];
        int ans[] = new int[100];
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        for (int i = 1; i <= 28; ++i) {
            f[i] = Main.get_fib(Main.get_fib(BigInteger.valueOf(i)));
        }
        while(T--> 0) {
            BigInteger W = cin.nextBigInteger();
            int cnt = 0;
            for (int i = 28; i >= 6; --i) {
                if(f[i].compareTo(W) <= 0) {
                    ans[++cnt] = i;
                    W = W.subtract(f[i]);
                }
            }
            if(W.compareTo(BigInteger.valueOf(1)) == 0) {
                ans[++cnt] = 1;
            }
            else if(W.compareTo(BigInteger.valueOf(2)) == 0){
                ans[++cnt] = 2;
                ans[++cnt] = 1;
            }
            else if(W.compareTo(BigInteger.valueOf(3)) == 0) {
                ans[++cnt] = 3;
                ans[++cnt] = 2;
                ans[++cnt] = 1;
            }
            else if(W.compareTo(BigInteger.valueOf(4)) == 0) {
                ans[++cnt] = 4;
                ans[++cnt] = 2;
                ans[++cnt] = 1;
            }
            else if(W.compareTo(BigInteger.valueOf(5)) == 0) {
                ans[++cnt] = 4;
                ans[++cnt] = 3;
                ans[++cnt] = 2;
                ans[++cnt] = 1;
            }
            else if(W.compareTo(BigInteger.valueOf(6)) == 0) {
                ans[++cnt] = 5;
                ans[++cnt] = 1;
            }
            else if(W.compareTo(BigInteger.valueOf(7)) == 0) {
                ans[++cnt] = 5;
                ans[++cnt] = 2;
                ans[++cnt] = 1;
            }
            else if(W.compareTo(BigInteger.valueOf(8)) == 0) {
                ans[++cnt] = 5;
                ans[++cnt] = 3;
                ans[++cnt] = 2;
                ans[++cnt] = 1;
            }
            else if(W.compareTo(BigInteger.valueOf(9)) == 0) {
                ans[++cnt] = 5;
                ans[++cnt] = 4;
                ans[++cnt] = 2;
                ans[++cnt] = 1;
            }
            else if(W.compareTo(BigInteger.valueOf(10)) == 0) {
                ans[++cnt] = 5;
                ans[++cnt] = 4;
                ans[++cnt] = 3;
                ans[++cnt] = 2;
                ans[++cnt] = 1;
            }
            else if(W.compareTo(BigInteger.ZERO)!=0){
                System.out.println(-1);
                continue;
            }
            for (int i = cnt; i >= 1; --i) {
                if(i == 1)
                    System.out.println(ans[i]);
                else 
                    System.out.print(ans[i]+" ");
            }
        }
    }

}

代码参考 https://www.cnblogs.com/widsom/p/10742707.html

2019南昌邀请赛 C. Angry FFF Party 大数矩阵快速幂+分类讨论

原文:https://www.cnblogs.com/stranger-/p/10746947.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!