MOD**2-оптимизация
Материал из Algocode wiki
Версия от 22:22, 25 сентября 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