CODE FESTIVAL 2016 Grand Final,G: FESTIVAL

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";
}