https://cf16-exhibition-final-open.contest.atcoder.jp/tasks/cf16_exhibition_final_g
昇順に並んでいる数列S{1,a,b,c,...X}があって、隣り合っている数の比がa(自然数)より小さいとします。
するとX以下の自然数NはSの線形結合で表されて、係数の和はO(a*loga(N))となります。
例えばS={1,2,5,13}でa=3,N=12なら
N=5*2+2*1と表されて係数の和は3となります。
帰納法で簡単に示せます。
これを使うと今回の問題が解けます。
FESTIVAL....LFESTIVAL...L...みたいなのを考えて、
f(k):=k個FESTIVA繰り返した文字列でFESTIVAが部分列として何個あるかとすると、
k個目のあと何個Lを置くかをckとしてN=c1f(1)+c2f(2)...cmf(m)となります。
fは簡単なdpで表されて、f(8)=1716らへんから隣接した数同士の比が2未満になることがわかります。
またm=600とするとf(600)=5*10^15なので、まずNを5*10^15未満にするのに200個位Lが必要で、
5*10^15から1716未満にするのに(2-1)log2(5*10^15)=50個程度必要です。あとはf(1)..f(7)で作れば良いのですが、これも100個程度でできるので、合計600*7+200+50+100=4550個程度でできます。
別に2の累乗じゃなくてもlogっぽい数列だったらこういうことできるんですね。
ll N; ll dp[610][8]; ll f[610]; ll ans[610]; void solve() { cin >> N; rep(i, 0, 7) dp[0][i] = 1; f[0] = 1; rep(i, 1, 600) { dp[i][6] = 1; rer(j, 6, 0) { rep(k, 0, i + 1) dp[i][j] += dp[k][j + 1]; } f[i] = dp[i][0] + f[i - 1]; } rer(i, 600, 0) { while(N - f[i] >= 0) { N -= f[i]; ans[i]++; } } string res; rep(i, 0, 600) { res += "FESTIVA"; rep(k, 0, ans[i]) res += 'L'; } cout << res << "\n"; }