递归模拟

题目描述
Dr. JYY has just created the Coffee Chicken strings, denoted as S(n). They are quite similar to the Fibonacci soup --- today's soup is made by mingling yesterday's soup and the day before yesterday's soup:S(1)="COFFEE";
S(2)="CHICKEN";

• S(n) = S(n-2) :: S(n-1), where :: denotes string concatenation.
  The length of S(n) quickly gets out of control as n increases, and there would be no enough memory in JYY's game console to store the entire string. He wants you to find 10 contiguous characters in S(n), starting from the kth character.

  输入描述:
  The first line of input is a single integer T (1≤T≤1000), denoting the number of test cases. Each of the following T lines is a test case, which contains two integers n, k (1≤n≤500,1≤k≤min{∣S(n)∣,10^12 }). |S| denotes the length of string S.
  输出描述:
  For each test case, print the answer in one line. If there are no enough characters from the kth character, output all characters until the end of the string.
  示例1
  输入
  2

• 4

• 7
  输出
  FEECHICKEN
  N

  题解
  题目与斐波那契数列有关但是因为Sn的增长到后面过于爆炸，因此不能直接求Sn然后求十个字符
  需要转换一下,请观察下面的规律
  A 1
  B 1
  AB 2
  BA 3
  ABBAB 5
  BABABBAB 8
  ABBABBABABBAB 13
  BABABBABABBABBABABBAB 21
  ABBABBABABBABBABABBABABBABBABABBAB 34
  BABABBABABBABBABABBABABBABBABABBABBABABBABABBABBABABBAB 45
  可以知道当前指向的位置大于a[n-2]就可以求a[n-1]的第k-a[n-2]个数（上面的数一数），如果小于等于a[n-2]就等于求a[n-2]的第几个数

代码示例

#include<iostream>
using namespace std;
using ll = long long;
ll a[700];
//mello函数记录Sn的字符串长度的值
void mello() {
    a[1] = 6;//6是COFFEE的长度
    a[2] = 7;//7是CHICKEN的长度
    for (int i = 3; i <= 60; i++) {
        a[i] = a[i - 1] + a[i - 2];//循环记录Sn的长度
    }
}

int main() {
    mello();
    int t;
    cin >> t;
    while (t--) {
        ll n, k;
        cin >> n >> k;
        //对于大于60的n，我们只需要取小的值替代即可，奇数用59，偶数用58
        //为什么用60？因为k最多到1e12，当Sn大于58时长度就超过了1e12
        if (n >= 60) {
            if (n % 2) n = 59;
            else n = 58;
        }
        for (ll i = k; i <= a[n] && i < k + 10; i++) {
            ll w = i, v = n;//w追踪当前位置，v追踪当前序列项
            while (v != 1 && v != 2) {//不断递归减小，直到v选择COFFEE或CHICKEN
                if (w > a[v - 2]) {
                    w = w - a[v - 2];
                    v -= 1;
                }
                else {
                    v -= 2;
                } 
            }
            if (v == 1) printf("%c", "COFFEE"[w - 1]);
            else if (v == 2) printf("%c", "CHICKEN"[w - 1]);
        }
        printf("\n");
    }
    return 0;
}