Submission #74297944

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int MAXK = 105;
const ll INF = (ll)2e18;  // 超过查询范围 1e18 即可

ll len[MAXK];  // 长度上限设为 > 2e18 时截断
ull cnt[MAXK][26];

string X, Y;

// 计算 S_k 的前 n 个字符中，字符 c 的出现次数
// n 用 ll，但查询范围是 1e18，在 ll 范围内
ull solve(int k, ll n, int c) {
	if (n <= 0)
		return 0;
	if (k == 1) {
		ull res = 0;
		for (ll i = 0; i < n && i < (ll)X.length(); i++)
			if (X[(size_t)i] == 'a' + c)
				res++;
		return res;
	}
	if (k == 2) {
		ull res = 0;
		for (ll i = 0; i < n && i < (ll)Y.length(); i++)
			if (Y[(size_t)i] == 'a' + c)
				res++;
		return res;
	}

	if (n <= len[k - 1]) {
		return solve(k - 1, n, c);
	} else {
		// 左半部分全取，右半部分递归
		// 注意：n - len[k-1] 可能很大，但递归深度有限
		return cnt[k - 1][c] + solve(k - 2, n - len[k - 1], c);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> X >> Y;
	int Q;
	cin >> Q;

	// 预处理
	len[1] = (ll)X.length();
	len[2] = (ll)Y.length();

	for (int c = 0; c < 26; c++) {
		char ch = 'a' + c;
		cnt[1][c] = 0;
		for (char x : X)
			if (x == ch)
				cnt[1][c]++;
		cnt[2][c] = 0;
		for (char y : Y)
			if (y == ch)
				cnt[2][c]++;
	}

	int K = 2;
	ll LIM = (ll)4e18;  // 上限，但实际 ll 最大约 9e18

	// 防止溢出：当长度将超过 4e18 时截断
	while (K < MAXK - 1 && len[K] < (ll)1e18) {  // 只需要到超过 1e18 即可
		K++;
		// 检查溢出
		if (len[K - 1] > LIM - len[K - 2]) {
			len[K] = LIM;
		} else {
			len[K] = len[K - 1] + len[K - 2];
		}

		for (int c = 0; c < 26; c++) {
			cnt[K][c] = min((ull)INF, cnt[K - 1][c] + cnt[K - 2][c]);
		}
	}

	// 确保 len[K] >= 1e18
	while (len[K] < (ll)1e18 && K < MAXK - 1) {
		K++;
		if (len[K - 1] > LIM - len[K - 2]) {
			len[K] = LIM;
		} else {
			len[K] = len[K - 1] + len[K - 2];
		}
		for (int c = 0; c < 26; c++)
			cnt[K][c] = min((ull)INF, cnt[K - 1][c] + cnt[K - 2][c]);
	}

	while (Q--) {
		ll L, R;
		char C;
		cin >> L >> R >> C;
		int c = C - 'a';

		ull ans = solve(K, R, c) - solve(K, L - 1, c);
		cout << ans << "\n";
	}

	return 0;
}

Submission Info

Judge Result