MOD**2-оптимизация
Материал из Algocode wiki
Давайте разберемся, как считать значения выражения по модулю так, чтобы это требовало минимального количества процессорных операций.
Если мы складываем значения, каждое из которых меньше $MOD$, то можно не брать их по модулю, а обходиться $if$-ами и вычитанием:
1 int res = a + b;
2 if (res >= MOD) {
3 res -= MOD;
4 }
В некоторых задачах, где надо считать сумму произведений величин, каждая из которых меньше $MOD$, бывает полезна следующая неасимптотическая оптимизация: Будем считать все произведения по модулю $MOD^2$, для подсчета сумм таких величин воспользуемся предыдущей техникой, а затем единожды возьмем ответ по модулю $MOD$. Такой трюк бывает полезен, к примеру, при перемножении матриц:
1 matrix multiple(matrix& a, matrix &b) {
2 int n = a.size();
3 int m = b[0].size();
4 int k = b.size();
5 matrix c(n, m);
6 for (int i = 0; i < n; i++) {
7 for (int j = 0; j < m; j++) {
8 int res = 0;
9 for (int t = 0; t < k; t++) {
10 res += a[i][t] * b[t][j];
11 if (res >= MOD2) {
12 res -= MOD2;
13 }
14 }
15 c[i][j] = res % MOD;
16 }
17 }
18 return res;
19 }
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s