B 咖啡坤

题目梳理

S[n] = S[n-2] + S[n-1]
对于给定的n和k,求S[n]的第k位

思路:

记 L[n]为S[n]的长度, 则有L[n] = L[n-2] + L[n-1]
因为S[n]是由前两项拼接而来:
如果 k<=L[n-2], 那么S[n]只需要看前面的一段S[n-2], 问题就变为了 n-2和k
如果 k>L[n-2], 那么就是求后面的S[n-1]的第k-L[n-2]位, 问题就变为了 n-1和k-L[n-2]

转移方程:

所以定义f(n,k)为S[n]的第k个字符
则有
f(n,k) = f(n-2,k), k<=L[n-2]
f(n,k) = f(n-1,k-L[n-2]), k>L[n-2]

ans = f(n,k)~f(n,k+10)

递归出口:

S[1]和S[2]是已知的
所以当n=1时,f(n,k)=S[1][k], 当n=2时,f(n,k)=S[2][k]

另外, 数据范围n有500, 但是k只有1e12, 打表发现L[56] > 1e12

所以 n最大是55, 如果n>56, 就可以直接缩减到56

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    static int I() {
        return sc.nextInt();
    }

    static long L() {
        return sc.nextLong();
    }

    static long[] L = new long[60];

    static {
        L[1] = 6;
        L[2] = 7;
        for (int i = 3; i <= 56; i++) {// L[56] > 1e12 >= k
          L[i] = L[i - 2] + L[i - 1];
        }
    }

    public static void main(String[] args) {
        int t = I();
        while (t-- > 0) solve();
        pw.flush();
    }


    static void solve() {
        int n = I();
        if (n > 56) n = 56;// L[56] > 1e12 >= k

        long k = L();
        StringBuilder sb = new StringBuilder();
        // ans = f(n,k)~f(n,k+10)
        for (int i = 0; i < 10 && k + i <= L[n]; i++) {
            sb.append(f(n, k + i));
        }
        pw.println(sb);
    }

    static String s1 = "COFFEE", s2 = "CHICKEN";

    static Character f(int n, long k) {
        if (n == 1) return s1.charAt((int) k - 1);
        if (n == 2) return s2.charAt((int) k - 1);
		// S[n] = S[n-2] + S[n-1]
        if (k <= L[n - 2]) {
            return f(n - 2, k);
        } else {
            return f(n - 1, k - L[n - 2]);
        }
    }
}