ABC450E Fibonacci String

思路

这道题要处理长度为 $10^{18}$ 的字符串，直接构造肯定不行。但仔细观察生成规则 $S_i = S_{i-1} + S_{i-2}$，发现字符串长度的增长符合斐波那契数列。

1. 长度极长

斐波那契数列增长是指数级的。即使 $|X|, |Y|$ 只有 1，大概不到 90 项，长度就会超过 $10^{18}$。
这意味着对于任何 $k \ge 90$，字符串 $S_k$ 的前 $10^{18}$ 个字符的结构是完全一样的。
题目问的是 $S_{10^{18}}$，其实我们只需要算到第一个长度超过 $10^{18}$ 的那一层（记为 max_k），后面的层数在查询范围内等价于这一层。

2. 预处理信息

我们可以先递推预处理出前 90 层左右的信息：

• len[k]：第 $k$ 层的长度。注意如果超过 $10^{18}$ 就直接存成一个很大的数（比如 $2 \times 10^{18}$），防止 long long 溢出。
• cnt[k][c]：第 $k$ 层中字符 c 出现的总次数。递推式很简单：cnt[k][c] = cnt[k-1][c] + cnt[k-2][c]。

3. 递归查询

要求 $[L, R]$ 区间内字符 $C$ 的个数，可以转化为前缀和相减：f(k, r, c) - f(k, l-1, c)。
其中 f(k, l, c) 表示在第 $k$ 层字符串的前 limit 个字符中，c 出现了多少次。

利用 $S_k = S_{k-1} + S_{k-2}$ 的结构递归：

1. 边界：如果 $k=1$ 或 $k=2$，直接遍历原始字符串 $X$ 或 $Y$ 统计前 l 个。
2. 在左半边：如果 l $\le$ len[k-1]，说明目标全在 $S_{k-1}$ 里，递归 f(k-1, l, c)。
3. 跨越两边：如果 l > len[k-1]，说明包含了完整的 $S_{k-1}$ 和 $S_{k-2}$ 的一部分。
   答案 = ($S_{k-1}$ 中 c 的总数) + f(k-2, limit - len[k-1], c)。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string x,y;
int q;
ll len[95],cnt[95][26];
int t;
ll f(int k,ll l,int c){
	if(l<=0)return 0;
	if(k==1){
		ll a=0;
		ll m=min(l,len[1]);
		for(ll i=0;i<m;i++)if(x[i]-'a'==c)a++;
		return a;
	}
	if(k==2){
		ll a=0;
		ll m=min(l,len[2]);
		for(ll i=0;i<m;i++)if(y[i]-'a'==c)a++;
		return a;
	}
	if(l<=len[k-1])return f(k-1,l,c);
	return cnt[k-1][c]+f(k-2,l-len[k-1],c);
}
int main(){
	cin>>x>>y>>q;
	len[1]=x.size();
	len[2]=y.size();
	for(int i=0;i<26;i++){
		cnt[1][i]=0;
		for(char c:x)if(c-'a'==i)cnt[1][i]++;
		cnt[2][i]=0;
		for(char c:y)if(c-'a'==i)cnt[2][i]++;
	}
	t=2;
	while(len[t]<2e18){
		int n=t+1;
		len[n]=len[t]+len[t-1];
		if(len[n]<0)len[n]=2e18;
		for(int i=0;i<26;i++)cnt[n][i]=cnt[t][i]+cnt[t-1][i];
		t++;
	}
	int s=t-1;
	while(s>2&&len[s-1]>=1e18)s--;
	while(len[s]<1e18)s++; 
	while(q--){
		ll l,r;
		char c;
		cin>>l>>r>>c;
		cout<<f(s,r,c-'a')-f(s,l-1,c-'a')<<"\n";
	}
}