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!