如何计算给定模式下k位置的数字？

Question

问题是：输入是 2 个数字 n (n<=10^5) and k, and you need to find the digit of position k (k<=10^15) in a(n). the pattern here is a(n) = n+2*a(n-1) in terms of string, not integer. So for example, a(1) is 1 -> a(2) = 211, a(3) = 3211211 等等。如果 a(n) 的长度< k then return -1

基于这个问题，我尝试根据a(n)的长度来做，我认为是2^n-1，但我很快发现它只适用于n<10. Then I tried to calculate the gap between the pairs of same numbers, but I don't think I can. Loop is not possible here since n can be up to 10^5 (this is also a problem on its own because when I tried large numbers in c++ it showed inf, not a number to calculate). Now I'm out of ideas.

编辑：这是问题的示例： 输入：5 4 所以 n=5 -> 数字是 5432112113211211432112113211211，第 4 位数字是 2，所以输出是 2

#include<fstream>
#include<cmath>
using namespace std;

int main() {
    ifstream fi;
    fi.open("input.inp");
    double n,k;
    fi >> n >> k;
    long long l = pow(2, n)-1;
    int ans;
    if (k>l) {
        ans = -1;
    }
    else if (k==1) {
        ans = n;
    }
    else {
        k = l+1-k;
        while (n>0) {
            if (log2(k+1)==floor(log2(k+1))) {
                ans = log2(k+1);
                break;
            }
            else {
                n-=1;
                if (k-(pow(2,n)-1)>=0) {
                    k-=(pow(2,n)-1);
                }
            }
        }
    }
    ofstream fo;
    fo.open("output.out");
    fo << ans;
    return 0;
}

Answer 1

首先，一些观察：

1.字符串大小以 n 为指数，因此 a(n) 需要 10000 位。 C++ 中最大的数字类型是 64 位的 uint64_t。
2. 幸运的是，对 k 的限制意味着我们只需考虑前 10^15 位数字，即 35 位，因此适合 uin64_t。
3. a(49) 是大小小于 10^15 的最后一个数字字符串。

接下来，简单的情况：如果 k <= d(n), where d(n) counts digits of the number n we can just read off the answer.

然后，对于 n > 50，我们可以安全地假设所需的数字必须位于 a(n-1) 的第一个分支中，因为 a(50) 及以上不再适合 10^^15。我们必须注意不要索引到 n 前缀，所以：

solution(k, n) | n > 50 = solution(k - d(n), n-1)

a(n-1) 的

n <= 50, k might also reach the 第二分支。因此：

solution(k, n) | n <= 50 && k - d(n) <= a(n-1) = solution(k - d(n), n-1)
               | otherwise                     = solution(k - a(n-1) - d(n), n-1)

为了提高效率，剩下的就是预先计算 a(n) 最多 50。 用 C++ 实现这一点留给读者作为练习。