Сумма xor цифр всех чисел от 1 до N, когда N очень велико.

Question

Учитывая 1 и N, нам нужно найти сумму значений XOR цифр всех чисел от 1 до N, Например, для N, нам необходимо вычислить функцию F

F(k){ 
    ans =0; 
    while(k>0){ 
     ans= ans^(k%10); 
     k/=10; 
    } 
    return ans; 
} 

для K в [1, N].

есть эффективный способ сказать. Насколько я могу думать, мы должны подсчитать количество раз, когда значение V приведет к XOR с использованием DP, но я не думаю о способе его реализации.

Просьба дать некоторую идею.

Пример: F (37) = 3^7 = 4

Примечание: N может быть как 10^18

Answer 1

Наивный подход занимает O(N*log10(N)) время, делая простой оптимизации вы можете получить O(N) время выполнения. Идея такова:

XOR всех цифр числа k цифр = XOR первых (k - 1) цифр^последней цифры.

Очевидно, что вы могли бы найти первые к - 1 цифры путем деления числа на 10, так что отношения становятся:

F(i) = F(i/10)^(i % 10)

Код:

result = 0 
for i = 1:N 
    dp[i] = dp[i/10]^i%10 
    result += dp[i] 

Answer 2

• Давайте вычислить немного другая вещь: сколько чисел от 1 до N имеет xor своих цифр, равных X для всех X from 0 to 15.

• Как только мы это узнаем, ответ на вашу проблему - это всего лишь сумма count[X] * X для всех действительных X.

• Как мы можем считать это эффективным? Мы будем использовать стандартное динамическое программирование .

• Мы можем рассматривать все числа как строки. Если мы поместим их нулями, чтобы их длина была равна числу цифр в N, мы можем сравнить их лексикографически.

• Состояние динамического программирования: (prefixLength, curXor, isSmaller) - число способов разместить первые prefixLength наиболее значимые цифры таким образом, что их Исключающее curXor. isSmaller истинно, если этот префикс меньше префикса N. В противном случае префикс равен N.

• Переход размещается еще раз. curXor изменяется тривиально. prefixLength увеличивается на единицу. Если значение isSmaller истинно, мы можем поместить любую цифру и продолжить. В противном случае мы не можем поставить цифру большего размера, чем цифра в этом положении в N. Если мы поместим один и тот же, isSmaller останется ложным. В противном случае это становится правдой.

• Позвольте L быть числом цифр в N. Чем точнее цифры f(L, X, 0) + f(L, X, 1), которые имеют xor своих цифр, равных X в диапазоне [1, N].

• Все готово! Число состояний составляет примерно 16 * L * 2, а число переходов составляет около 16 * L * 2 * 10. В качестве L = O(log N) временная сложность этого решения составляет O(log N), что выглядит довольно неплохо.

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