Считать биты, установленные в системе счисления Фибоначчи?

Question

Мы знаем, что каждое неотрицательное десятичное число может быть однозначно представлено суммой чисел Фибоначчи (здесь нас интересует минимальное представление, т. Е. Последовательные числа Фибоначчи не принимаются в представлении числа, а также берется каждое число Фибоначчи)не более одного в представлении).

Например:

1->  1
2-> 10
3->100
4->101, here f1=1 , f2=2 and f(n)=f(n-1)+f(n-2);

, поэтому каждое десятичное число может быть представлено в системе Фибоначчи в виде двоичной последовательности.Если мы последовательно запишем все натуральные числа в системе Фибоначчи, мы получим последовательность, подобную этой: 110100101… Это называется «битовая последовательность натуральных чисел Фибоначчи».

Моя задача состоит в подсчете числа раз, которое1 появляется в первых N битах этой последовательности. Поскольку N может принимать значение от 1 до 10 ^ 15, могу ли я сделать это без сохранения последовательности Фибоначчи?

, например: если N равно 5, ответ равен 3.

Answer 1

Так что это всего лишь предварительный набросок алгоритма. Это работает, когда верхняя граница сама по себе является числом Фибоначчи, но я не уверен, как адаптировать его для общих верхних границ. Надеюсь, кто-то может улучшить это.

Общая идея состоит в том, чтобы взглянуть на структуру кодировок Фибоначчи. Вот первые несколько цифр:

     0
     1
    10
   100
   101
  1000
  1001
  1010
 10000
 10001
 10010
 10100
 10101
100000

Инвариант в каждом из этих чисел состоит в том, что никогда не бывает пары последовательных единиц. Учитывая этот инвариант, мы можем увеличивать от одного числа к следующему, используя следующий шаблон:

1. Если последняя цифра равна 0, установите ее на 1.
2. Если последняя цифра равна 1, то поскольку последовательных цифр 1 нет, установите последнюю цифру на 0, а следующую цифру на 1.
3. Устраните любые удвоенные 1 с, установив их оба на 0 и установив следующую цифру на 1, повторяя, пока все удвоенные 1 не будут устранены.

Причина того, что это важно, в том, что свойство (3) говорит нам кое-что о структуре этих чисел. Давайте еще раз рассмотрим первые несколько чисел в кодировке Фибоначчи. Посмотрите, например, на первые три числа:

  00
  01
  10

Теперь посмотрите на все четырехбитные числа:

1000
1001
1010

Следующий номер будет иметь пять цифр, как показано здесь:

1011 & rarr; 1100 & rarr; 10000

Интересно отметить, что число с четырьмя цифрами равно числу значений с двумя цифрами. Фактически, мы получаем четырехзначные числа, просто добавляя префикс самое большее двухзначное число к 10.

Теперь посмотрите на трехзначные числа:

000
001
010
100
101

И посмотрите на пятизначные числа:

10000
10001
10010
10100
10101

Обратите внимание, что пятизначные числа - это просто трехзначные числа с префиксом 10.

Это дает нам очень интересный способ подсчитать, сколько 1s. В частности, если вы посмотрите на (k + 2) -значные числа, каждое из них является просто k-значным числом с префиксом 10. Это означает, что если во всех k-значных числах имеется общее количество B 1, то общее количество B в числах, состоящих из k + 2 цифр, равно B плюс количество k-значных чисел, поскольку мы просто воспроизведение последовательности с дополнительным 1, добавленным к каждому номеру.

Мы можем использовать это для вычисления числа 1 в кодировках Фибоначчи, которые имеют не более k цифр в них. Хитрость заключается в следующем - если для каждого количества цифр мы отслеживаем

1. Сколько чисел имеет самое большее столько цифр (назовите это N (d)), и
2. Сколько единиц представляют числа с не более чем d цифрами (назовите это B (d)).

Мы можем использовать эту информацию для вычисления этих двух частей информации для еще одной цифры. Это прекрасное повторение DP. Первоначально, мы посеем это следующим образом. Для одной цифры N (d) = 2 и B (d) равно 1, поскольку для одной цифры числа 0 и 1. Для двух цифр N (d) = 3 (есть только одно двузначное число, 10, и два однозначных числа 0 и 1) и B (d) равно 2 (одно из 1, одно из 10). Оттуда у нас есть

• N (d + 2) = N (d) + N (d + 1). Это связано с тем, что число чисел, содержащее до d + 2 цифр, представляет собой число чисел, содержащее до d + 1 цифр (N (d + 1)), плюс числа, образованные путем добавления префикса 10 к числам с d цифрами (N ( г)) * * тысячу пятьдесят-один
• B (d + 2) = B (d + 1) + B (d) + N (d) (общее количество 1 бит в количестве не более d + 2 равно общему количеству 1 бит в числа длиной не более d + 1, плюс дополнительные, которые мы получаем из чисел, состоящих всего из d + 2 цифр)

Например, мы получаем следующее:

 d     N(d)      B(d)
---------------------
 1       2          1
 2       3          2
 3       5          5
 4       8         10
 5      13         20

Мы действительно можем это проверить. Для однозначных чисел используется всего один бит. Для двузначных чисел есть два (1 и 10). Для трехзначных чисел существует пять единиц (1, 10, 100, 101). Для четырехзначных чисел существует 10 (пять предыдущих, плюс 1000, 1001, 1010). Расширение этого внешнего вида дает нам последовательность, которую мы хотели бы.

Это очень легко вычислить - мы можем вычислить значение для k цифр за время O (k) с использованием только O (1) памяти, если мы будем использовать пространство ранее. Поскольку числа Фибоначчи экспоненциально быстро растут, это означает, что если у нас есть какое-то число N и мы хотим найти сумму всех битов 1 с наибольшим числом Фибоначчи, меньшим, чем N, мы можем сделать это во времени O (log N) и пространстве O (1). * +1061 *

Тем не менее, я не уверен, как адаптировать это для работы с общими верхними границами. Тем не менее, я настроен оптимистично, что есть какой-то способ сделать это. Это прекрасное повторение, и просто должен быть хороший способ его обобщить.

Надеюсь, это поможет! Спасибо за потрясающую проблему!

Answer 2

Чтобы не решить 3 проблемы.Каждый следующий сложнее предыдущего, каждый использует результат предыдущего.

1.Сколько из них установлено, если вы записываете каждое число от 0 до fib [i] -1.

Назовите это dp[i].Давайте посмотрим на числа

     0
     1
    10
   100
   101
  1000
  1001
  1010 <-- we want to count ones up to here
 10000

Если вы запишите все числа вплоть до fib [i] -1, сначала вы запишите все числа до fib [i-1] -1 (dp [i-1]), то вы пишете последний блок чисел.Есть ровно число [i-2] из этих чисел, каждое из которых имеет единицу на первой позиции, поэтому мы добавляем fib [i-2], и если вы удалите эти числа

000
001
010

, то удалите ведущиенули, вы можете видеть, что каждое число от 0 до fib [i-2] -1 записано.Числа одного там равны dp [i-2], что дает нам:

dp[i] = fib[i-2] + dp[i-2] + dp[i-1];

2.Сколько из них установлено, если вы записываете каждое число от 0 до n.

     0
     1
    10
   100
   101
  1000
  1001 <-- we want to count ones up to here
  1010 

Позволяет назвать это solNumber(n)

Предположим, что ваш номер равен f [i] + x, где f [i] - максимально возможное число Фибоначчи.Тогда anser, если dp [i] + solNumber (x).Это можно доказать так же, как в пункте 1.

3.Сколько единиц указано в первых n цифрах.

3a.Сколько чисел имеют длину представления ровно l

, если l = 1, ответ равен 1, иначе его fib [l-2] + 1. Вы можете заметить, что если вы удалите старшие, а затем все начальные нули, выбудет иметь каждое число от 0 до fib [l-1] -1.Точно фиб [l] числа.

// Конец 3a

Теперь вы можете найти такое число m, чем, если вы напишите все числа от 1 до m, ихобщая длина будет <= n.Но если вы напишите все от 1 до m + 1, общая длина будет> n.Решите проблему вручную для m + 1 и добавьте solNumber (m).

Все 3 проблемы решены в O (log n)

#include <iostream>

using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define RFOR(i, b, a) for(int i = b - 1; i >= a; --i)
#define REP(i, N) FOR(i, 0, N)
#define RREP(i, N) RFOR(i, N, 0)

typedef long long Long;


const int MAXL = 30;



long long fib[MAXL];

//How much ones are if you write down the representation of first fib[i]-1 natural numbers
long long dp[MAXL];

void buildDP()
{
    fib[0] = 1;
    fib[1] = 1;
    FOR(i,2,MAXL)
        fib[i] = fib[i-1] + fib[i-2];


    dp[0] = 0;
    dp[1] = 0;
    dp[2] = 1;

    FOR(i,3,MAXL)
        dp[i] = fib[i-2] + dp[i-2] + dp[i-1];
}

//How much ones are if you write down the representation of first n natural numbers
Long solNumber(Long n)
{   
    if(n == 0)
        return n;
    Long res = 0;
    RREP(i,MAXL)
        if(n>=fib[i])
        {           
            n -= fib[i];
            res += dp[i];
            res += (n+1);
        }
    return res;
}

int solManual(Long num, Long n)
{
    int cr = 0;

    RREP(i,MAXL)
    {
        if(n == 0)
            break;

        if(num>=fib[i])
        {
            num -= fib[i];
            ++cr;
        }

        if(cr != 0)
            --n;
    }
    return cr;
}

Long num(int l)
{
    if(l<=2)
        return 1;
    return fib[l-1];
}

Long sol(Long n)
{
    //length of fibonacci representation
    int l = 1;
    //totatl acumulated length
    int cl = 0;
    while(num(l)*l + cl <= n)
    {
        cl += num(l)*l;
        ++l;
    }   
    //Number of digits, that represent numbers with maxlength
    Long nn = n - cl;

    //Number of full numbers;
    Long t = nn/l;

    //The last full number
    n = fib[l] + t-1;

    return solNumber(n) + solManual(n+1, nn%l);



}

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    buildDP();

    Long n;
    while(cin>>n)
        cout<<"ANS: "<<sol(n)<<endl;
    return 0;
}

Answer 3

Вот способ подсчитать все однозначные числа в наборе чисел с точностью до заданной длины цифры. Мне кажется, это разумная отправная точка для решения

Рассмотрим 10 цифр. Начните с письма;

0000000000

Теперь мы можем превратить некоторое количество этих нулей в единицы, оставив последнюю цифру всегда равной 0. Рассмотрим возможности в каждом конкретном случае.

0 Есть только один способ выбрать 0 из них. Суммирование 1-битов в этом одном случае дает 0.

1 Существует {9 выберите 1} способов превратить один из нулей в один. Каждый из них дает 1.

2 Существует {8 вариантов выбора 2} способов превратить два нуля в один. Каждый из них дает 2.

...

5 Существует {5 вариантов выбора 5} способов превратить пять нулей в единицы. Каждый из них вносит 5 в число битов.

Легко думать об этом как о проблеме листов. Строка из 10 нулей - это доска 10x1, которую мы хотим выложить с квадратами 1x1 и 2x1 домино. Выбор некоторого числа нулей равным единице - это то же самое, что выбрать некоторые плитки для домино. Мое решение тесно связано с Identity 4 в «Доказательствах, которые действительно имеют значение» Бенджамина и Куинна.

Второй шаг Теперь попробуйте использовать описанную выше конструкцию для решения исходной задачи

Предположим, мы хотим, чтобы один бит в первых 100100010 битах (число, конечно, в представлении Фибоначчи). Начните с пересчета суммы для всех способов замены х на нули и единиц в 10xxxxx0. Чтобы сверхкомпенсировать перерасчет, вычтите количество для 10xxx0. Продолжить процедуру пересчета и сверхкомпенсации.

Answer 4

Эта проблема имеет динамическое решение, что иллюстрируется проверенным алгоритмом ниже.Следует помнить несколько моментов, которые очевидны в коде:

Наилучшее решение для каждого числа i будет получено с использованием числа Фибоначчи f, где f == i ИЛИ, где f меньше i, чем онодолжно быть f и наибольшее число n <= f: i = f + n. </p>

Обратите внимание, что последовательность fib запоминается по всему алгоритму.

public static int[] fibonacciBitSequenceOfNaturalNumbers(int num) {
    int[] setBits = new int[num + 1];
    setBits[0] = 0;//anchor case of fib seq
    setBits[1] = 1;//anchor case of fib seq
    int a = 1, b = 1;//anchor case of fib seq
    for (int i = 2; i <= num; i++) {
        int c = b;
        while (c < i) {
            c = a + b;
            a = b;
            b = c;
        }//fib
        if (c == i) {
            setBits[i] = 1;
            continue;
        }
        c = a;
        int tmp = c;//to optimize further, make tmp the fib before a
        while (c + tmp != i) {
            tmp--;
        }
        setBits[i] = 1 + setBits[tmp];
    }//done

    return setBits;
}

Тест с:

 public static void main(String... args) {
    int[] arr = fibonacciBitSequenceOfNaturalNumbers(23);
    //print result
    for(int i=1; i<arr.length; i++)
        System.out.format("%d has %d%n", i, arr[i]);
  }

РЕЗУЛЬТАТ ТЕСТА: у меня есть x установленных битов

1 has 1
2 has 1
3 has 1
4 has 2
5 has 1
6 has 2
7 has 2
8 has 1
9 has 2
10 has 2
11 has 2
12 has 3
13 has 1
14 has 2
15 has 2
16 has 2
17 has 3
18 has 2
19 has 3
20 has 3
21 has 1
22 has 2
23 has 2

РЕДАКТИРОВАТЬ НА ОСНОВЕ КОММЕНТАРИИ:

//to return total number of set between 1 and n inclusive
//instead of returning as in original post, replace with this code

            int total = 0;
            for(int i: setBits)
                total+=i;
            return total;

Answer 5

Это не полный ответ, но он описывает, как вы можете сделать этот расчет без использования грубой силы.

Представление Фибоначчи Fn представляет собой 1, за которым следуют n-1 нули.

Для чисел от Fn до, но не включая F(n+1), число единиц состоит из двух частей:

1. Есть F(n-1) таких чисел, поэтому F(n-1) ведущих 1.
2. Двоичные цифры после первых чисел - это просто двоичные представления всех чисел, вплоть до F(n-1).

Итак, если мы вызовем общее количество битов в последовательности вплоть до, но не включая nth числа Фибоначчи an, то мы получим следующую рекурсию:

a(n+1) = an + F(n-1) + a(n-1)

Вы также можете легко получить количество битов в последовательности до Fn.

Если для получения (но не прохождения) N требуется k чисел Фибоначчи, то вы можете посчитать эти биты по приведенной выше формуле и, после некоторых дальнейших манипуляций, уменьшить проблему до подсчета количества бит в оставшаяся последовательность.

Answer 6

[Редактировать]: В основном я следовал за свойством, что для любого числа n, которое должно быть представлено в базе Фибоначчи, мы можем разбить его на n = n - x, где x - это наибольшее число Фибоначчи, чуть меньшее * 1004. *. Используя это свойство, любое число может быть разбито в битовой форме.

Первый шаг - найти десятичное число, в котором заканчивается бит Nth. Мы можем видеть, что все числа между числами Фибоначчи F(n) и F(n+1) будут иметь одинаковое количество битов. Используя это, мы можем предварительно рассчитать таблицу и найти соответствующее число.

Допустим, у вас есть десятичное число D, в котором есть бит Nth. Теперь пусть X будет наибольшим числом Фибоначчи, меньшим или равным D. Чтобы найти биты для всех чисел от 1 до D, мы представляем его как ... X+0, X+1, X+2, .... X + D-X. Итак, все X будут представлены 1 в конце, и мы разбили проблему на гораздо меньшую подзадачу. То есть нам нужно найти все установленные биты до D-X. Мы продолжаем делать это рекурсивно. Используя ту же логику, мы можем построить таблицу с соответствующим количеством установленных битов для всех чисел Фибоначчи (до предела). Мы будем использовать эту таблицу для определения количества установленных битов от 1 до X. Итак,

Findsetbits(D) { // finds number of set bits from 1 to D.
find X; // largest fibonacci number just less than D
ans = tablesetbits[X];
ans += 1 * (D-x+1); // All 1s at the end due to X+0,X+1,...
ans += Findsetbits(D-x); 
return ans;
}

Я попробовал несколько примеров вручную и увидел образец.

Я кодировал грубое решение, которое я проверил вручную на N <= 35. Для больших чисел оно работает довольно быстро, хотя я не уверен, что оно верное. Если это проблема онлайн-судьи, пожалуйста, дайте ссылку на нее. </p>

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

#define pb push_back
typedef long long LL;
vector<LL>numbits;
vector<LL>fib;
vector<LL>numones;
vector<LL>cfones;

void init() {
    fib.pb(1);
    fib.pb(2);
    int i = 2;
    LL c = 1;
    while ( c < 100000000000000LL ) {
        c = fib[i-1] + fib[i-2];
        i++;
        fib.pb(c);
    }
}


   LL answer(LL n) {
    if (n <= 3) return n;
    int a = (lower_bound(fib.begin(),fib.end(),n))-fib.begin();
    int c = 1;
    if (fib[a] == n) {
        c = 0;
    }
    LL ans = cfones[a-1-c] ;
    return ans + answer(n - fib[a-c]) + 1 * (n - fib[a-c] + 1);
}
int fillarr(vector<int>& a, LL n) {
    if (n == 0)return -1;
    if (n == 1) {
        a[0] = 1;
        return 0;
    }
    int in = lower_bound(fib.begin(),fib.end(),n) - fib.begin(),v=0;
    if (fib[in] != n) v = 1;
    LL c = n - fib[in-v];
    a[in-v] = 1;
    fillarr(a, c);
    return in-v;
}
int main() {
    init();
    numbits.pb(1);
    int b = 2;
    LL c;
    for (int i = 1; i < fib.size()-2; i++) {
        c = fib[i+1] - fib[i] ;
        c = c*(LL)b;
        b++;
        numbits.pb(c);
    }
    for (int i = 1; i < numbits.size(); i++) {
        numbits[i] += numbits[i-1];
    }
    numones.pb(1);
    cfones.pb(1);
    numones.pb(1);
    cfones.pb(2);
    numones.pb(1);
    cfones.pb(5);
    for (int i = 3; i < fib.size(); i++ ) {
        LL c = 0;
        c += cfones[i-2]+ 1 * fib[i-1];
        numones.pb(c);
        cfones.pb(c + cfones[i-1]);
    }
    for (int i = 1; i < numones.size(); i++) {
        numones[i] += numones[i-1];
    }
    LL N;
    cin>>N;
    if (N == 1) {
        cout<<1<<"\n";
        return 0;
    }
    // find the integer just before Nth bit
    int pos;
    for (int i = 0;; i++) {
        if (numbits[i] >= N) {
            pos = i;
            break;
        }
    }

    LL temp = (N-numbits[pos-1])/(pos+1);
    LL temp1 = (N-numbits[pos-1]);
    LL num = fib[pos]-1 + (temp1>0?temp+(temp1%(pos+1)?1:0):0);
    temp1 -= temp*(pos+1);
    if(!temp1) temp1 = pos+1;
    vector<int>arr(70,0);
    int in = fillarr(arr, num);
    int sub = 0;
    for (int i = in-(temp1); i >= 0; i--) {
        if (arr[i] == 1)
            sub += 1;
    }
    cout<<"\nNumber answer "<<num<<" "<<answer(num) - sub<<"\n";
    return 0;
}

Answer 7

1. Вычислить m, число, отвечающее за (N + 1) -й бит последовательности.Вычислите вклад m в счет.

2. Мы сократили задачу до подсчета числа одного бита в диапазоне [1, m).В стиле деревьев интервалов разделите этот диапазон на O (log N) поддиапазонов, каждый из которых имеет связанный глобус, например 10100 ????это соответствует представлениям точно чисел, принадлежащих этому диапазону.Вклад префиксов легко вычислить.

3. Задача сводится к подсчету общего количества T (k) одного бита во всех словах Фибоначчи длины k (т. Е.Причем часть глобусов).T (k) определяется следующим повторением.

   T(0) = 0
   T(1) = 1
   T(k) = T(k - 1) + T(k - 2) + F(k - 2)
   

Mathematica говорит, что есть решение в закрытой форме, но оно выглядит ужасно и не требуется для этого polylog (N) -время алгоритм.

Answer 8

Здесь O ((log n) ^ 3).

Позволяет вычислить, сколько чисел помещается в первых N битах

Представьте, что у нас есть функция:

long long number_of_all_bits_in_sequence(long long M); 

Она вычисляет длину созданной "битовой последовательности Фибоначчи натуральных чисел"по всем числам, которые не больше M.

С помощью этой функции мы можем использовать бинарный поиск, чтобы найти, сколько чисел помещается в первые N бит.

Сколько битов в представлении 1первых чисел M

Позволяет создать функцию, которая вычисляет, сколько чисел <= M имеют 1 в k-м бите. </p>

long long kth_bit_equal_1(long long M, int k);

Сначала позволяет предварительно обработать результаты этой функции для всех малых значений,скажем, M <= 1000000. </p>

Реализация для M> PREPROCESS_LIMIT:

long long kth_bit_equal_1(long long M, int k) {
   if (M <= PREPROCESS_LIMIT) return preprocess_result[M][k];

   long long fib_number = greatest_fib_which_isnt_greater_than(M);
   int fib_index = index_of_fib_in_fibonnaci_sequence(fib);

   if (fib_index < k) {
      // all numbers are smaller than k-th fibbonacci number
      return 0;
   }

   if (fib_index == k) {
      // only numbers between [fib_number, M] have k-th bit set to 1
      return M - fib_number + 1;       
   } 

   if (fib_index > k) {
      long long result = 0;

      // all numbers between [fib_number, M] have bit at fib_index set to 1
      // so lets subtrack fib_number from all numbers in this interval
      // now this interval is [0, M - fib_number]
      // lets calculate how many numbers in this inteval have k-th bit set.
      result += kth_bit_equal_1(M - fib_number, k);

      // don't forget about remaining numbers (interval [1, fib_number - 1])
      result += kth_bit_equal_1(fib_number - 1, k);

      return result;
   }
}

Сложность этой функции - O (M / PREPROCESS_LIMIT).

Обратите внимание, что при повторном появленииодним из добавлений всегда является одно из чисел Фиббоначи.

kth_bit_equal_1(fib_number - 1, k);

Таким образом, если мы запомним все вычисленные результаты, сложность улучшится до T (N) = T (N / 2) + O (1).T (n) = O (log N).

Давайте вернемся к number_of_all_bits_in_sequence

Мы можем слегка изменить kth_bit_equal_1, чтобы он также считал биты равными 0.