Боря программирует

const int mod = 998244353;

В олимпиадном программировании в задачах на комбинаторику, где ответ может быть очень большим, часто просят посчитать остаток от деления этого ответа на какое-нибудь простое число (например, 998244353). Например, если ответ на задачу 10^100, то нужно вывести (10^100) % 998244353 = 876867878 вместо очень длинного числа. Идея в том, что если отстаток от деления совпал с правильным, то и исходный ответ, наверное, правильный. Но зато все вычисления можно проводить в 64-битных типах и не нужна длинная арифметика.

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

Например, чтобы посчитать x / 998244353, вначале предподсчитаем magic_number = 2^87 / 998244353 + 1 = 155014655926305585. Тогда x / 998244353 = (x * magic_number) / (2^87) = (x * magic_number) >> 87. Заметим, что x * magic_number вообще говоря не вмещатся в 64-битный тип, поэтому, если попытаться написать такой код вручную, то нужно было бы использовать 128 битную арифметику. Но на самом деле, ассемблерная инструкция imul и так при перемножении 64-битных чисел получает 128 битный результат, но кладет его в два разных 64-битных регистра. Так что для получения реального ответа нужно взять старший из регистров результата и сдвинуть его на 87 - 64 = 23 бита.

Хорошо что нынче не нужно понимать все это самому, и компилятор может это соптимизировать за нас!

Но буквально вчера обнаружил, что если объявить модуль как int mod = 998244353;, а не const int mod = 998244353;, то компилятор перестает делать эту оптимизацию, использует инструкцию idiv, и код становится в полтора* раза медленнее.

Идея в том, что если не добавить модификатор const, то, даже если мы никогда не изменяем переменную, компилятор не имеет права думать, что она всегда будет одинаковой. Например, мы можем в другом файле написать extern int mod;, а потом ее поменять. При этом код в исходном файле должен продолжить работать и использовать новое значение.

Так что когда объявляете модуль, всегда используйте const: const int mod = 998244353!

👍107❤22🤯20💯8🔥5😐4👏2🤔2

www.tgoop.com/bminaiev_blog/81

15K viewsOct 27, 2024 at 14:12

const int mod = 998244353;

В олимпиадном программировании в задачах на комбинаторику, где ответ может быть очень большим, часто просят посчитать остаток от деления этого ответа на какое-нибудь простое число (например, 998244353). Например, если ответ на задачу 10^100, то нужно вывести (10^100) % 998244353 = 876867878 вместо очень длинного числа. Идея в том, что если отстаток от деления совпал с правильным, то и исходный ответ, наверное, правильный. Но зато все вычисления можно проводить в 64-битных типах и не нужна длинная арифметика.

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

Например, чтобы посчитать x / 998244353, вначале предподсчитаем magic_number = 2^87 / 998244353 + 1 = 155014655926305585. Тогда x / 998244353 = (x * magic_number) / (2^87) = (x * magic_number) >> 87. Заметим, что x * magic_number вообще говоря не вмещатся в 64-битный тип, поэтому, если попытаться написать такой код вручную, то нужно было бы использовать 128 битную арифметику. Но на самом деле, ассемблерная инструкция imul и так при перемножении 64-битных чисел получает 128 битный результат, но кладет его в два разных 64-битных регистра. Так что для получения реального ответа нужно взять старший из регистров результата и сдвинуть его на 87 - 64 = 23 бита.

Хорошо что нынче не нужно понимать все это самому, и компилятор может это соптимизировать за нас!

Но буквально вчера обнаружил, что если объявить модуль как int mod = 998244353;, а не const int mod = 998244353;, то компилятор перестает делать эту оптимизацию, использует инструкцию idiv, и код становится в полтора* раза медленнее.

Идея в том, что если не добавить модификатор const, то, даже если мы никогда не изменяем переменную, компилятор не имеет права думать, что она всегда будет одинаковой. Например, мы можем в другом файле написать extern int mod;, а потом ее поменять. При этом код в исходном файле должен продолжить работать и использовать новое значение.

Так что когда объявляете модуль, всегда используйте const: const int mod = 998244353!

BY Боря программирует