Вопрос: Подсчет битов, установленных в системе чисел Фибоначчи?


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

Например:

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.


10


источник


Ответы:


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

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

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

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

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

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

  00
  01
  10

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

1000
1001
1010

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

1011 → 1100 → 10000

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

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

000
001
010
100
101

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

10000
10001
10010
10100
10101

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

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

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

  1. Сколько чисел имеет не более многих цифр (назовем это N (d)) и
  2. Сколько 1s представляют числа с не более 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-значных чисел используется 1 бит. Для 2-значных чисел есть два (1 и 10). Для 3-значных чисел есть пять 1s (1, 10, 100, 101). Для четырехзначных чисел есть 10 (пять предыдущих, плюс 1000, 1001, 1010). Расширение этого наружу дает нам последовательность, которая нам нужна.

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

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

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


4



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

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

Назовите это dp[i], Давайте посмотрим на цифры

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

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

000
001
010

затем удалите начальные нули, вы увидите, что записывается каждое число от 0 до фила [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;
}

1



  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 говорит, что есть закрытое решение, но оно выглядит ужасно и не нужно для этого Полилог (N) -time  алгоритм.


0



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

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

Для чисел из Fn до, но не включая F(n+1), число 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,

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


0



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

Первый шаг - найти десятичное число такое, что 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. Он работает довольно быстро для больших чисел, хотя я не могу быть уверен, что это правильно. Если это проблема онлайн-судьи, дайте ссылку на нее.

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

0



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

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

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

long long number_of_all_bits_in_sequence(long long M); 

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

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

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

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

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

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

Реализация для 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.


0



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

Рассмотрим 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 битах (это число, конечно, в представлении Фибоначчи). Начните с перерасчета суммы для всех способов заменить x на нули и единицы в 10xxxxx0. Чтобы перекомпенсировать перерасчет, перечислите счетчик для 10xxx0. Продолжайте процедуру перерасчета и сверхкомпенсации.


0