Ответ 1

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

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

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

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

• Если последняя цифра равна 0, установите ее в 1.
• Если последняя цифра равна 1, то, поскольку не существует последовательных 1s, установите последнюю цифру в 0, а следующую цифру - 1..
• Устраните любые удвоенные 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 цифр. Трюк заключается в следующем: если для каждого числа цифр мы отслеживаем

• Сколько чисел имеет не более многих цифр (назовем это N (d)) и
• Сколько 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).

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

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

Ответ 2

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

1. Сколько из них задано, если вы записываете каждое число из 0 в фид [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] этих чисел, каждый из которых имеет одну в первой позиции, поэтому мы добавляем фиб [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;
}

Ответ 3

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

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

Предположим, что у нас есть функция:

long long number_of_all_bits_in_sequence(long long M); 

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

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

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

Позволяет создать функцию, которая вычисляет, сколько чисел <= 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.

Ответ 4

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

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

• Мы привели задачу к подсчету общего числа 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) -time.

Ответ 5

[Edit]: В основном я следил за свойством, которое для любого числа 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. Итак, в 1 в конце будет отображаться все x, и мы сломали проблему в гораздо меньшую подзадачу. То есть, нам нужно найти все установленные биты до 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;
}

Ответ 6

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

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

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

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

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

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

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

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

Ответ 7

Здесь можно пересчитать все цифры в наборе чисел до заданной длины длины. Это кажется мне разумной отправной точкой для решения

Рассмотрим 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. Продолжайте процедуру перерасчета и сверхкомпенсации.

Ответ 8

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

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

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

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;