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

我试图用组合和计数子集来解决相当复杂的问题。首先，我们给定集合A = {1,2,3，… N}，其中N <= 10

^（18）。现在，我们要计算其表示中没有连续数字的子集。

假设N = 3，而A = {1,2,3}。总共有2 ^

3个子集，但我们不想计算子集（1,2），（2,3）和（1,2,3）。因此，对于这个问题，我们总共要回答5，因为我们只想计算剩余的5个子集。这些子集是（空子集），（1），（2），（3），（1,3）。我们也想以10

^ 9 + 7为模来打印结果。

我当时以为应该使用带有两个状态的动态规划来解决这个问题（我们是否采用第i个元素），但是后来我看到N可以上升到10 ^

18，所以我以为应该解决这个问题使用数学公式。您能给我一些提示，我应该从哪里开始获取公式。

提前致谢。

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

他们得出的结论是，集合{1,2,3 … n}中的非连续子集的数量为fib（n + 2），其中fib是为数量n + 2计算斐波那契数列的函数。您对n =

3的解符合此解。如果您可以实现Fibonacci算法，则可以解决此问题，但是解决一个最大为10 ^ 18的数字的问题仍然是一个挑战。

如此处评论所述，您可以在Hacker Earth上查看快速翻倍算法。

它将在O（log n）中找到斐波那契数。