题目描述

解题思路

本题可以采用递归的方法。
因为本题中的$x$非常大，有$10^{18}$，所以必须在递归的同时计算出$P$ 的个数，不能先
求出字符串再统计$P$ 的个数
递归如下：

ll get(ll n, ll x) {    // 用len[n]记录当i为n的时候字符串的长度
    // 如果n为0，返回1
    // 如果x为1，返回0
    /* 如果x <= 1 + len[n - 1] 表示着str_n的前x位和str_(n-1)的P的个数一样，
    就返回(get(n - 1, x - 1)*/
    /*如果x为2 + len[n - 1] 表示着str_n的前x位P的个数是
    str_(n-1)的P的个数+1，返回(1 + get(n - 1, len[n - 1])*/
    /*如果x为2 + 2 * len[n - 1] 表示着str_n的前x位P的个数是
    str_(n-1)的P的个数+剩下的，返回1 + get(n - 1, len[n - 1]) + get(n - 1, x - 2 - len[n - 1])*/
    /*如果x就是str_n的长度，就返回1 + 2 * get(n - 1, len[n - 1])*/
}

下面就是整体代码:

#include <iostream>
#include <climits>
using namespace std;
typedef long long ll;
ll len[55];
ll get(ll n, ll x) {
    if (n == 0) return 1;
    if (x == 1) return 0;
    if (x <= 1 + len[n - 1]) return get(n - 1, x - 1);
    if (x == 2 + len[n - 1]) return 1 + get(n - 1, len[n - 1]);
    if (x <= 2 + 2 * len[n - 1]) return 1 + get(n - 1, len[n - 1]) + get(n - 1, x - 2 - len[n - 1]);
    if (x == 3 + 2 * len[n - 1]) return 1 + 2 * get(n - 1, len[n - 1]);
}
int main() {
    ll n, x;
    cin >> n >> x;
    len[0] = 1;
    for (int i = 1; i <= n; i++) len[i] = len[i - 1] * 2 + 3;
    cout << get(n, x);
    return 0;
}