csp7连测day7T1

给两个字符串, A[0], B[0]

然后定义 A[i] = A[i - 1] + B[i - 1], B[i] = A[i - 1] + B[i - 1];
T 个询问

每次求 A[935] 的第 x 个数字

其实这题只要递归做就好了，关键是 $ 2^{935} $ 这个数字太大了……
考场上想到的办法是直接求出使得 $ A,B $ 大小最接近 $1e15$ 的一个数，但是有可能出现上一个还没到1e15, 下一个已经是负数了。。就错误了，但是我们可以直接预处理出从 1-935 的字符串长度，太长用 inf 代替，然后直接在函数内部判断大小并递归…

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int N = 1e3 + 5, M = 1e4 + 5;

ll lenA[N], lenB[N];
char A[M], B[M];

char getA(int n, ll x);
char getB(int n, ll x);

char getA(int n, ll x)
{
	if (!n) return A[x];

	if (x < lenA[n - 1]) return getA(n - 1, x);
	return getB(n - 1, x - lenA[n - 1]);
}

char getB(int n, ll x)
{
	if (!n) return B[x];

	if (x < lenB[n - 1]) return getB(n - 1, x);
	return getA(n - 1, x - lenB[n - 1]);
}

int main()
{
	int n, m, t;
	scanf("%d%d%d", &n, &m, &t);
	scanf("%s%s", &A, &B);

	lenA[0] = n, lenB[0] = m;
	for (int i = 1; i < N; i++)
		lenA[i] = lenB[i] = min(inf, lenA[i - 1] + lenB[i - 1]);

	while (t--)
	{
		ll x;
		scanf("%lld", &x);
		putchar(getA(935, x - 1));
		putchar('\n');
	}
	return 0;
}