Всем от новичка до профессионала приходится иметь дело с модульной арифметикой в очень широком спектре задач, от хеширования строк, до подсчета дп на деревьях (да-да, сейчас кто-то скажет, что все сводится к хэшам и комбе, но тема от этого не менее часто встречается).
Мне же еще с самых первых дней в олимпиадном программировании не нравились задачи с модульной арифметикой, забудешь один раз ans %= MOD; И сиди с WA, и, либо минусом по задаче, либо просто трать время на дебаг, поэтому всегда приходилось внимательно расписывать формулы. Однажды меня познакомили с хэшами и удобным способом их написания: функциями необходимыми, чтобы не забыть о модулях по типу add(x, y), sub(x, y) и mul(x, y). Код, хоть и стал выглядеть гораздо лучше, но все еще оставался нечитаемым, да и задумываться о прикладных мелочах, пока считаешь математику, не хочется, поэтому логическим продолжением данной темы с функциями (имхо) будет класс модульных интов. Я предлагаю следующую реализацию: #include "iostream" template<class T, T MOD> class ModInt{ public: ModInt(const T &x = T(0)) : x_(x % MOD) {} friend ModInt& operator+=(ModInt &a, const ModInt &b){ a.x_ += b.x_; if (a.x_ >= MOD) a.x_ -= MOD; return a; } friend ModInt operator+(ModInt a, const ModInt &b){ return a += b; } friend ModInt& operator-=(ModInt &a, const ModInt &b){ a.x_ -= b.x_; if (a.x_ < 0) a.x_ += MOD; return a; } friend ModInt operator-(ModInt a, const ModInt &b){ return a -= b; } friend ModInt& operator*=(ModInt &a, const ModInt &b){ a.x_ = a.x_ * b.x_ % MOD; return a; } friend ModInt& operator*(ModInt a, const ModInt &b){ return a *= b; } ModInt& operator=(const ModInt &b){ x_ = b.x_; return *this; } friend std::istream &operator>>(std::istream &in, ModInt &a){ in >> a.x_; a.x_ %= MOD; return in; } friend std::ostream &operator<<(std::ostream &out, const ModInt &a){ out << a.x_; return out; } ModInt& operator++(){ ++x_; if (x_ == MOD) x_ = 0; return *this; } ModInt& operator--(){ --x_; if (x_ == -1) x_ = MOD — 1; return *this; } ModInt operator++(int ){ ModInt old = *this; ++x_; if (x_ == MOD) x_ = 0; return old; } ModInt operator--(int ){ ModInt old = *this; --x_; if (x_ == -1) x_ = MOD — 1; return old; } private: T x_; };
Теперь все, что вам нужно сделать в задаче, чтобы ваш ответ считался по модулю — это написать: #define int ModInt<int64_t, 998244353>
WARNING: Константы по типу INF или подобные могут испортиться, думайте, когда используете этот define
Да, такой #define использовать плохо, но кто мне запретит. Конечно, теперь решение работает незначительно медленнее, например, потому что счетчики в циклах for теперь тоже работают по модулю (а вы их 100% часто используете), но, если вам не нужно пихать задачу, то жизнь вам это хуже не сделает.
Плюсы: 1) Хэши теперь можно писать почти как в 2009, когда еще не был известен anti-hash test против модулей 2^k 2) Любую комбинаторику из тетрадки можно просто перенести в код без лишней мороки
Минусы: 1) Незначительно ухудшает скорость программы
Лично для меня + сильно перевешивают -. Если придется загонять задачу, то, скорее всего, так и так придется хардкодить. Здесь же сильно упрощена работа с любой арифметикой и код становится гораздо более читаемым.
Далее можно развить класс, добавив модульное деление, т.е. умножение на обратное по модулю, но это я уже оставлю в качестве тривиального упражнения читателю)
В заключение: Конечно, на туре такое писать вряд ли быстрее, чем написать пару функций или, вообще, все считать в одной строке, но не всегда цель — решить задачу как можно быстрее, иногда этим процессом хочется насладиться, или для поиска бага повысить читаемость кода, да и не всегда пишешь задачи в какой-то ограниченный по времени тур, иногда закинуть готовый шаблон гораздо приятнее, чем переписывать все формулы по модулю на фул)
