南昌ICPC邀请赛C.Angry FFF Party – 高精暴力

本来以为还是签完到就开始自闭，没想到今天的邀请赛还摸出一道C。这题看提交数其实不多，而且题目表达也挺复杂。简单来说，就是把一个数W拆成若干个Fib(Fib(x))之和，其中x各不相同。题目数据是1 \leq W \leq 10^{100000}，乍一看好像很夸张。其实去算Fib \left( x \right) \leq 10^{100000}就会发现，其实也就x \leq 317811，再算Fib \left( x \right) \leq 317811，发现其实也就28个数。不过这28个数真的挺长的，打表还真打不下，好在Fib现算一遍也就O(logN)。

然后拆数我写的就很low了，由于字典序最小，我就用了O\left( n^2 \right)的朴素方法。其实只有2和5需要处理，但是第一次交的时候好像我其它地方漏了个条件，于是WA了。后来保险就用了，总复杂度是O\left( 28^2 T + \log N \right)。

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    // 打表，前28项
    final static int[] ind = {0,1,2,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811};
    static boolean[] inS = new boolean[30];
    static boolean[] used = new boolean[30];
    static BigInteger[] ff = new BigInteger[30];
    static int sCnt;

    static boolean check(BigInteger W, int st) {
        int curCheck = st;
        sCnt = 0;
        for (int i = 1; i < ind.length; i++) used[i] = false;
        while (W.compareTo(BigInteger.ZERO) > 0 && curCheck > 0) {
            if (!inS[curCheck] && W.compareTo(ff[curCheck]) >= 0) {
                W = W.subtract(ff[curCheck]);
                used[curCheck] = true;
                sCnt++;
            }
            curCheck--;
        }
        if (sCnt > 0 && W.equals(BigInteger.ZERO)) {
            for (int i = 1; i < ind.length; i++) inS[i] = inS[i] || used[i];
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int curInd, cnt;
        BigInteger fn_2, fn_1, fn;
        fn_2 = BigInteger.ONE;
        fn_1 = BigInteger.ONE;
        ff[1] = BigInteger.ONE; ff[2] = BigInteger.ONE; ff[3] = BigInteger.ONE;
        cnt = 2; curInd = 4;
        while (curInd < ind.length) {
            fn = fn_2.add(fn_1);
            fn_2 = fn_1;
            fn_1 = fn;
            cnt++;
            if (cnt == ind[curInd]) {
                ff[curInd] = fn;
                curInd++;
            }
        }
        // 读入
        Scanner sc = new Scanner(System.in);
        int T, curCheck;
        BigInteger W;
        T = sc.nextInt();
        while (T-- > 0) {
            W = sc.nextBigInteger();
            sCnt = 0; // 集合S大小
            // 初始化inS
            for (int i = 1; i < ind.length; i++) inS[i] = false;
            // 检查
            if (!check(W, ind.length - 1)) {
                // 失败
                System.out.println("-1");
                continue;
            }
            // 对每个数，向前分割
            BigInteger num;
            curCheck = ind.length - 1;
            while (curCheck > 0) {
                while (curCheck > 0 && !inS[curCheck]) curCheck--;
                if (!inS[curCheck]) break;
                // inS[curCheck] = true
                if (check(ff[curCheck], curCheck - 1)) {
                    inS[curCheck] = false;
                }
                curCheck--;
            }
            // 重新计算sCnt
            sCnt = 0;
            for (int i = 1; i < ind.length; i++) if (inS[i]) sCnt += 1;
            // 打印
            for (int i = 1; i < ind.length; i++) {
                if (inS[i]) {
                    System.out.print(i);
                    sCnt--;
                    if (sCnt > 0) System.out.print(' ');
                }
            }
            System.out.println();
        }
    }
}