MOD**2-оптимизация

Материал из Algocode wiki
Версия от 13:13, 27 сентября 2019; KiKoS (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Если мы складываем значения, каждое из которых меньше $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