计算没有连续元素的子集总数 [英] Count the total number of subsets that don't have consecutive elements

问题描述

我正在尝试通过组合运算和计数子集来解决非常复杂的问题.首先，我们给定集合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，所以我认为应使用数学公式求解.能给我一些提示，我应该从哪里开始获取公式.

谢谢.

解决方案

看看在Hacker Earth上快速翻倍算法.
它将在O(log n)中找到斐波那契数.

I'm trying to solve pretty complex problem with combinatorics and counting subsets. First of all let's say we have given set A = {1, 2, 3, ... N} where N <= 10^(18). Now we want to count subsets that don't have consecutive numbers in their representation.

Example

Let's say N = 3, and A = {1,2,3}. There are 2^3 total subsets but we don't want to count the subsets (1,2), (2,3) and (1,2,3). So in total for this question we want to answer 5 because we want to count only the remaining 5 subsets. Those subsets are (Empty subset), (1), (2), (3), (1,3). Also we want to print the result modulo 10^9 + 7.

What I've done so far

I was thinking that this should be solved using dynamical programming with two states (are we taking the i-th element or not), but then I saw that N could go up to 10^18, so I was thinking that this should be solved using mathematical formula. Can you please give me some hints where should I start to get the formula.

Thanks in advance.

解决方案

Take a look at How many subsets contain no consecutive elements? on the Mathematics Stack Exchange.

They come to the conclusion that the number of non-consecutive subsets in the set {1,2,3...n} is the fib(n+2) where fib is the function computing the Fibonacci sequence for the number n+2. Your solution to n=3 conforms to this solution. If you can implement the Fibonacci algorithm, then you can solve this problem, but solving the question for a number as large as 10^18 will still be a challenge.

As mentioned in the comments here, you can check out the fast doubling algorithm on Hacker Earth.
It will find Fibonacci numbers in O(log n).

这篇关于计算没有连续元素的子集总数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！