はじめに
解説記事は初めてです。誤りを含んでいる場合があるので、誤りがあった場合には、twitterのDMでお知らせください。よろしくお願いします。
ABC450-E Fibonacci String (diff:1352)
問題概要
文字列$X,Y$について$S_0=X,S_1=Y,S_{i}=S_{i-1}S_{i-2}$とするとき、$S_{10^{18}}$の$L_i$文字目から$R_i$文字目に文字$c$がいくつ含まれるか聞いてくるクエリがたくさん飛んでくるので答えてください
制約
- $1\leq |X|,|Y|\leq 10^4$
- $1\leq Q\leq 10^5$
- $1\leq L_i\leq R_i\leq 10^{18}$
自力で解きたい方はここで引き返してください。
考察
公式解説では再帰を使う方法が解説されていましたが、この解法では再帰を使いません。
方針
$R$文字目までに含まれている$c$の数と$L-1$文字目までに含まれている$c$の数の差を取れば、この問題に解答することができます。よって、任意の位置$x$について1文字目から$x$文字目に$c$が何回出現するかをカウントすることができればよいです(ここまでは公式解説と同様です)。
カウント方法
まず、ブロックを定義しておきます。$S_{\infty}=YXYYX...$となるのでこの$X,Y$それぞれがブロックです。0-indexedとします。
$|S_{10^{18}}|$は明らかに$10^{18}$より大きく、$S_{i-1}$は$S_{i}$のprefixになるので今回の制約の中では$S_{\infty}$を考えてるとしてよいです。
ここで、$S_{\infty}$の$X,Y$は無限フィボナッチ列の$1,0$に対応します。
また、無限フィボナッチ列のn項目($=f_n$)(0-indexed)は
2+\lfloor (n+1)\varphi \rfloor-\lfloor (n+2)\varphi \rfloor
であるため、これを0から$n$まで累積和することで$n$項目までに含まれる1の数がわかり、$S_{\infty}$の$k$ブロック目までの$X$の出現回数がわかります。この式は愚直に足し合わせるとO(n)かかりますが、以下のように工夫します。
\begin{align}
&\sum_{k=0}^{n} \left(2+\lfloor (k+1)\varphi \rfloor-\lfloor (k+2)\varphi \rfloor\right)\\
=& \sum_{k=0}^{n} 2+\sum_{k=0}^{n} \lfloor (k+1)\varphi \rfloor-\sum_{k=0}^{n} \lfloor (k+2)\varphi \rfloor\\
=& 2\left(n+1\right)+\sum_{k=0}^{n} \lfloor (k+1)\varphi \rfloor-\sum_{k=1}^{n+1} \lfloor (k+1)\varphi \rfloor\\
=& 2\left(n+1\right)+\lfloor \varphi \rfloor-\lfloor (n+2)\varphi \rfloor\\
=& 2\left(n+1\right)+1-\lfloor (n+2)\varphi \rfloor\\
=& 2n+3-\lfloor (n+2)\varphi \rfloor\\
\end{align}
なお、ここで3項目は$\varphi=\frac{1+\sqrt{5}}{2}$を直接持って計算するのではなく$f(x)=x\varphi=\frac{x+\sqrt{5x^2}}{2}$として$f(n+2)$を計算します(浮動小数点の誤差をなくすため)。
$X$の出現回数がわかれば$Y$の出現回数がわかるため、総文字数がわかります。
これにより、ブロック数で二分探索することで、$x$文字目が何ブロック目に属する($m$とします)のかがわかります。
仕上げで$m-1$ブロック目までの$c$の出現回数とはみでてる分の$c$の出現回数を足し合わせれば任意の位置$x$について1文字目から$x$文字目までに何回$c$が出現するかがわかります。はみ出てる分については上の一般項を使えば$X,Y$どちらなのかがわかります。
これは、公式解説と同様に$X,Y$それぞれについて、ある英文字がそれより前に何回出てるかというのをa～zで前計算すれば計算することができます。
補足
$f(x)$について、以下のように実装しています。
long long iphi(long long r){
__int128 x = (__int128)5 * r * r;
long long s = sqrtl((long double)x);
while((__int128)(s+1)*(s+1) <= x) s++;
while((__int128)s*s > x) s--;
return (r + s) / 2;
}
sqrtlは誤差が出る場合があるので、続くwhile文で補正しています。この補正はsの値を小さくするループについてたかだか1回しか発生しません。(実は、sの値を大きくするループについては今回の制約では発生しません。)
提出(424ms)
参考文献
u64 の平方根を f64 で計算するやつに関して - えびちゃんの日記(Hatena Blog) 2026年3月24日閲覧
さいごに
どうでもいいですが私は$\phi$より$\varphi$のほうが好きです。