HELP !!!!, I am scared of MOD

→ Обратите внимание

До соревнования
Codeforces Round 1123 (Div. 2)
2 дня
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	Qingyu	156
2	nik_exists	150
2	maspy	150
4	Um_nik	143
5	Errichto	139
6	adamant	137
7	AmShZ	135
8	maroonrk	133
9	BledDest	132
10	qwexd	129

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя dhanunjaygurram12340

HELP !!!!, I am scared of MOD

Автор dhanunjaygurram12340, история, 14 месяцев назад, По-английски

This might super dumb to ask ,but I really need some clear cut answer to this nightmare of mine

Due to this one operation I lost confidence even in questions that I am capable of solving and many Wrong Submissions during the contests where I am having trouble to use this mod (sounds stupid)

Just a simple question....

WHEN & WHERE(i.e in which part of the code) DO I NEED TO USE (% MOD)?

Are there any golden rules on where to use %mod

Also what is the guarantee (or any proof kinda thing) that using %mod at a particular place do not change my final answer??

#modulo, #modular_theory

dhanunjaygurram12340
14 месяцев назад
17

Комментарии (12)

Показать архивные | Написать комментарий?

HCCoder

14 месяцев назад, скрыть # |

← Rev. 2 →

you can use it always with * and +. (a — b) % mod => (a%mod — b%mod + mod)%mod

→ Ответить

HCCoder

14 месяцев назад, скрыть # ^ |

← Rev. 2 →

be careful with -, since it is not just (a — b) % mod. Because a — b might be less than zero

→ Ответить

dhanunjaygurram12340

14 месяцев назад, скрыть # ^ |

So any proof that using %mod at * , + == final_answer_without_mod%mod

Or is it just '%' obeys distributive property with +,* ?

→ Ответить

HCCoder

14 месяцев назад, скрыть # ^ |

If x >= mod, you must use x%mod, but if x < mod, x%mod == x and nothing would be changed, so you always can use %. And I suggest using % always, not only in the end, as it can prevent owelflow

→ Ответить

scanfex

14 месяцев назад, скрыть # |

It's ok bro. I'm scared of it too

→ Ответить

Mindeveloped

14 месяцев назад, скрыть # |

Use a modulo integer class

→ Ответить

dhanunjaygurram12340

14 месяцев назад, скрыть # ^ |

Thanks for the suggestion

→ Ответить

imsuck12

14 месяцев назад, скрыть # |

← Rev. 2 →

Use modint as suggested by Mindeveloped, or write functions that apply mod for you and use them everywhere for your calculation. This can be better if you're going to offline competitions where you don't have a modint template at hand.

Spoiler

const int mod = 1e9 + 7;

// Assumes inputs are in the range [0, mod)
int inv(int a) {
    int b = mod, x = 1, y = 0;
    while (b) {
        x = exchange(y, x - a / b * y);
        a = exchange(b, a % b);
    }
    return x < 0 ? x + mod : x;
}
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int sub(int a, int b) { return add(a, mod - b); }
int mul(int a, int b) { return 1LL * a * b % mod; }
int divi(int a, int b) { return mul(a, inv(b)); }

Example:

dp[i] = add(dp[i], mul(dp[i-1], dp[i-2]));

→ Ответить

dhanunjaygurram12340

14 месяцев назад, скрыть # ^ |

Thanks, having a class modint makes it less time consuming and less error prone

→ Ответить

Atombeou123

14 месяцев назад, скрыть # ^ |

yes this is what i need to do better in offline competition

→ Ответить

Senku

14 месяцев назад, скрыть # |

Using something like

This

constexpr long long mod = 1e9 + 7;
inline long long Mod(long long num) {
    num %= mod;
    return num < 0 ? num + mod : num;
}

inline long long Inv(long long num) {
    assert(num > 0);
    num %= mod;
    long long p = mod - 2;
    long long res = 1;
    while (p) {
        if (p & 1) {
            res *= num;
            res %= mod;
        }
        num *= num;
        num %= mod;
        p >>= 1;
    }
    return res;
}

inline long long Add(long long a, long long b) {
    return Mod(Mod(a) + Mod(b));
}

inline long long Sub(long long a, long long b) {
    return Mod(Mod(a) - Mod(b));
}

inline long long Mul(long long a, long long b) {
    return Mod(Mod(a) * Mod(b));
}

inline long long Div(long long a, long long b) {
    return (Mod(a) * Inv(b)) % mod;
}

might help, instead of using +, -, * and / to perform the operations safely. (/ is mostly just useless in case of modular operations)

(I know the above code applies Mod too many times and might increase overhead but I just like to keep the functions safe for big or negative inputs unless the time limit is too strict)

Additionally, avoid using int for variables that store modular values, as multiplication (or addition or subtraction) with big numbers can cause overflow.

As for when and where to apply %, you want to apply it after any operation whose result can be >= mod. If you use the * operator, make sure you don't do more than one multiplication (or addition or subtraction) without modding the previous result. For example,

Spoiler

long long mod = 1e9 + 7;
long long a = 1e9;
long long wrong = (a * a * a) % mod; // gives wrong result since a * a * a is 1e27, which exceeds even the limit of long long
long long right = (((a * a) % mod) * a) % mod; // gives right answer since  a * a = 1e18 is modded immidiately, before exceeding the limit of long long

Also, in case of negative numbers (like result of a subtraction), make sure you you add mod if res % mod returns a negative number.

However if you just use the functions given above, you don't have to pay too much attention to these details.

There might be other ways like using a modular integer class, but this is just what I'm comfortable with. Hope it helps!

→ Ответить

MOD-Operation

14 месяцев назад, скрыть # |

I think the title is a bit rude

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 23.09.2026 17:20:27 (g2).

Десктопная версия, переключиться на мобильную.

При поддержке