计算没有连续元素的子集总数

看看有多少子集不包含连续元素？在数学堆栈交换上。

他们得出的结论是，集合{1,2,3 … n}中的非连续子集的数量为fib（n + 2），其中fib是为数量n + 2计算斐波那契数列的函数。您对n =
3的解符合此解。如果您可以实现Fibonacci算法，则可以解决此问题，但是解决一个最大为10 ^ 18的数字的问题仍然是一个挑战。

如此处评论所述，您可以在Hacker Earth上查看快速翻倍算法。
它将在O（log n）中找到斐波那契数。