Всем от новичка до профессионала приходится иметь дело с модульной арифметикой в очень широком спектре задач, от хеширования строк, до подсчета дп на деревьях (да-да, сейчас кто-то скажет, что все сводится к хэшам и комбе, но тема от этого не менее часто встречается).↵
↵
Мне же еще с самых первых дней в олимпиадном программировании не нравились задачи с модульной арифметикой, забудешь один раз `ans %= MOD`; И сиди с WA, и, либо минусом по задаче, либо просто трать время на дебаг, поэтому всегда приходилось внимательно расписывать формулы. Однажды меня познакомили с хэшами и удобным способом их написания: функциями необходимыми, чтобы не забыть о модулях по типу add(x, y), sub(x, y) и mul(x, y). Код, хоть и стал выглядеть гораздо лучше, но все еще оставался нечитаемым, да и задумываться о прикладных мелочах, пока считаешь математику, не хочется, поэтому логическим продолжением данной темы с функциями (имхо) будет класс модульных интов. ↵
Я предлагаю следующую реализацию:↵
↵
``` c++↵
#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) Незначительно ухудшает скорость программы↵
↵
Лично для меня + сильно перевешивают -. Если придется загонять задачу, то, скорее всего, так и так придется хардкодить. Здесь же сильно упрощена работа с любой арифметикой и код становится гораздо более читаемым.↵
↵
Далее можно развить класс, добавив модульное деление, т.е. умножение на обратное по модулю, но это я уже оставлю в качестве тривиального упражнения читателю)↵
↵
В заключение: Конечно, на туре такое писать вряд ли быстрее, чем написать пару функций или, вообще, все считать в одной строке, но не всегда цель — решить задачу как можно быстрее, иногда этим процессом хочется насладиться, или для поиска бага повысить читаемость кода, да и не всегда пишешь задачи в какой-то ограниченный по времени тур, иногда закинуть готовый шаблон гораздо приятнее, чем переписывать все формулы по модулю на фул)
↵
Мне же еще с самых первых дней в олимпиадном программировании не нравились задачи с модульной арифметикой, забудешь один раз `ans %= MOD`; И сиди с WA, и, либо минусом по задаче, либо просто трать время на дебаг, поэтому всегда приходилось внимательно расписывать формулы. Однажды меня познакомили с хэшами и удобным способом их написания: функциями необходимыми, чтобы не забыть о модулях по типу add(x, y), sub(x, y) и mul(x, y). Код, хоть и стал выглядеть гораздо лучше, но все еще оставался нечитаемым, да и задумываться о прикладных мелочах, пока считаешь математику, не хочется, поэтому логическим продолжением данной темы с функциями (имхо) будет класс модульных интов. ↵
Я предлагаю следующую реализацию:↵
↵
``` c++↵
#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) Незначительно ухудшает скорость программы↵
↵
Лично для меня + сильно перевешивают -. Если придется загонять задачу, то, скорее всего, так и так придется хардкодить. Здесь же сильно упрощена работа с любой арифметикой и код становится гораздо более читаемым.↵
↵
Далее можно развить класс, добавив модульное деление, т.е. умножение на обратное по модулю, но это я уже оставлю в качестве тривиального упражнения читателю)↵
↵
В заключение: Конечно, на туре такое писать вряд ли быстрее, чем написать пару функций или, вообще, все считать в одной строке, но не всегда цель — решить задачу как можно быстрее, иногда этим процессом хочется насладиться, или для поиска бага повысить читаемость кода, да и не всегда пишешь задачи в какой-то ограниченный по времени тур, иногда закинуть готовый шаблон гораздо приятнее, чем переписывать все формулы по модулю на фул)
