h
Получается инверсия второго массива - это чисто чтобы константу улучшить?
Size: a a a
2020 May 26
KK
Да это просто как тебе писать удобнее
KK
Как хочешь - так и пишешь
KK
Меньше мест багу схватить
KK
Если ты только увеличиваешь - ты менее вероятно перепутаешь место где тебе увеличивать, а где уменьшать
I
@webreh пасиба
2020 May 27
mq
1. правда, что тут везде опечатка и на самом деле везде log m, opt(i, m/2), ...?
2. правда ведь, что если C(k, j) = C(k), то оно решается без логарифма просто поддержанием префиксных минимумов?
2. правда ведь, что если C(k, j) = C(k), то оно решается без логарифма просто поддержанием префиксных минимумов?
К
Посоветуйте быстрый алгоритм. Перепробовал много алгоритмов, но по времени не проходит. Задача: задаётся степень двойки n и граница m. Числа получаются конкатенацией всех чисел от 1 до текущего(1, 12, 123, 1234...). Текущий от 1 до m. И нужно найти кол-во чисел, которые делятся на 2 в степени n. N не больше 6, а m не больше 10^18.
/¯
Камиль
Посоветуйте быстрый алгоритм. Перепробовал много алгоритмов, но по времени не проходит. Задача: задаётся степень двойки n и граница m. Числа получаются конкатенацией всех чисел от 1 до текущего(1, 12, 123, 1234...). Текущий от 1 до m. И нужно найти кол-во чисел, которые делятся на 2 в степени n. N не больше 6, а m не больше 10^18.
Поинт первый. Очевидно что на делимость на 2^n влияют только последние n цифр. Дальше небольшой перебор по тому, сколько чисел подряд влезает в n цифр
D
Камиль
Посоветуйте быстрый алгоритм. Перепробовал много алгоритмов, но по времени не проходит. Задача: задаётся степень двойки n и граница m. Числа получаются конкатенацией всех чисел от 1 до текущего(1, 12, 123, 1234...). Текущий от 1 до m. И нужно найти кол-во чисел, которые делятся на 2 в степени n. N не больше 6, а m не больше 10^18.
То есть у нас получается массив из 18 чисел, правильно?
D
И по нему надо искать или я чего-то не понял?
К
Ща полное условие скину
К
К
лимит времени - 1сек
MB
Камиль
Ща полное условие скину
Ну, тебе все правильно сказало. Надо перебрать последние N цифр. Если образованное ими число делится на 2**N, то надо посчитать кол-во способов добиться такого суффикса
AS
Камиль
сначала нужно спрашивать откуда задача, на случай если это ongoing contest
AS
кстати, решается и для произвольного не очень большого модуля
D
Ну, тебе все правильно сказало. Надо перебрать последние N цифр. Если образованное ими число делится на 2**N, то надо посчитать кол-во способов добиться такого суффикса
Для меня не очевидно, почему последние n цифр числа на это влияют. Я понимаю, что в битовом представлении последние n нулей должно быть, чтобы число делилось на степень двойки и можно тогда перестановку префикса посчитать
D
Или я неправ?
MB
Для меня не очевидно, почему последние n цифр числа на это влияют. Я понимаю, что в битовом представлении последние n нулей должно быть, чтобы число делилось на степень двойки и можно тогда перестановку префикса посчитать
Потому что число выглядит как
10**n*(head) + tail.
Если мы возьмем по модулю 2**n, то первое слагаемое станет 0. То есть только хвостик из N цифр влияет не делимость
10**n*(head) + tail.
Если мы возьмем по модулю 2**n, то первое слагаемое станет 0. То есть только хвостик из N цифр влияет не делимость