By madhur4127, history, 6 months ago, , TL;DR This article features Modular class which can be conviniently used for modular arithmetic more "naturally".

Motivation

Recent round featured an interesting problem 1081C - Colorful Bricks (if you plan to solve it, read this later). Combinatoric solution requires you to calculate: Many contestants failed pretest because of missing modulo operation somewhere in code.

Solution

Many contestants use functions like add(ll a, ll b) or mul(ll a , ll b) which makes implementation somewhat clumsy.

I present you an alternate approach using Modular class.

template <int MOD=998'244'353>
struct Modular {
int value;
static const int MOD_value = MOD;

Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}
Modular(long long a, long long b) : value(0){ *this += a; *this /= b;}

Modular& operator+=(Modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
Modular& operator-=(Modular const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
Modular& operator*=(Modular const& b) {value = (long long)value * b.value % MOD;return *this;}

friend Modular mexp(Modular a, long long e) {
Modular res = 1; while (e) { if (e&1) res *= a; a *= a; e >>= 1; }
return res;
}
friend Modular inverse(Modular a) { return mexp(a, MOD - 2); }

Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
friend Modular operator+(Modular a, Modular const b) { return a += b; }
friend Modular operator-(Modular a, Modular const b) { return a -= b; }
friend Modular operator-(Modular const a) { return 0 - a; }
friend Modular operator*(Modular a, Modular const b) { return a *= b; }
friend Modular operator/(Modular a, Modular const b) { return a /= b; }
friend std::ostream& operator<<(std::ostream& os, Modular const& a) {return os << a.value;}
friend bool operator==(Modular const& a, Modular const& b) {return a.value == b.value;}
friend bool operator!=(Modular const& a, Modular const& b) {return a.value != b.value;}
};


Using this code can be written more naturally in modular field just like integers. This implementation simplifies usage, for example:

// Chained Multiplication or Successive Simple Multiplication
Modular<998244353> a=1, m=123456789;
a *= m * m * m; // a = 519994069
// Inverse
a=inverse(m) // a=25170271
// fractions
Modular<> frac=(1,2); // frac=1*2^(-1) % 998244353 = 499122177
// Modular exponentiation
Modular<> power(2);
power=mexp(power,500); // power = 616118644


Credits to Jakube and here's the link to original source. Link: Modular.h  Comments (16)
 » 6 months ago, # | ← Rev. 3 →   I have seen similar implementations before, but I'm not sure if performance is not an issue. Do you have benchmarks comparing this to the non-wrapped implementation, in terms of both time and memory usage?I think having this in a critical loop (which runs, say 10^8 times) might be problematic, but I'm not sure; C++ compilers can do a lot of magic.
•  » » that's c++. such abstractions do not cost anything here.
•  » » » Isn't there overhead for the function call? Or can we be certain it is inlined
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   you are right, overhead for function calls is possible but for such trivial function I just assume they are inlined (I use such class for several years, didn't have any problem).
•  » » I use a similar class. In my experience the abstraction doesn't noticeably reduce efficiency compared to manually applying the same operations, but it can cause you to use more operations that you actually need. In particular, when taking the sum of N numbers, it is more efficient to first sum them in long long, then reduce that sum, than to reduce after every addition.
 » 6 months ago, # | ← Rev. 5 →   Exactly what Wave said.Perfomance in many cases of modular tasks is an issue and you should avoid copying by const Modular& rather using plain const Modular (since it doesn't really matter whether you put const here or not, you can keep it if you want compliler to help you a little) in most of your operators.See this: this. Although being too unrealistic, you should generally avoid passing references to classes where sizeof(class) is around a single pointer due to a perfomance overhead over plain copy of that class.P.S. I don't see this struct Modular  as a good solution because such class makes it significantly harder to pass ints to functionsP.P.S. and yeah, specialization for long long modulo would've been really cool, since this is something really lame to implement over and over
•  » » 6 months ago, # ^ | ← Rev. 3 →   Since all the methods and friend functions are implemented in the class, they will be inlined by default, and there is no difference in passing argument by reference or by value.
•  » » » being inline and being inlined is more or less orthogonal
 » integer do not form field btw
 » 6 months ago, # | ← Rev. 2 →   Your implementation is very limiting. First, only int modulo is supported, no long long or any custom big integer class. Second, it won't work if the modulo isn't fixed, i.e. given in the input file.I have similar class that can be found for example in these submissions: 26577783 24552744. Indeed, it's very convenient and I never faced any performance issues.
•  » » Another issue is that it relies on the modulo being prime (the inverse is found using fermat's).
•  » » » yes, this works for prime modulo which is very common otherwise you can replace inverse with extended euclid.Because it is not very common where you need to find inverse in non-prime modulo (not for problems focused on extended euclid), so focusing on speed fermat is used.
•  » » btw you may use std::integral_constant when modulo is constant instead of creating new class manually
•  » » 1 . Considering general modulo (1e9+7, 9998244353), long long is not supported as multiplication function will change to somewhat like code below, which will not be efficient in case of common integer mod. Codell mulmod(ll a, ll b, ll c=MOD) { if(a>b) {ll temp=b; b=a; a=temp;} ll x = 0, y = a % c; while (b > 0) { if (b&2LL) x = (x + y) % c; y = (y<<1) % c; b >>= 1; } return x; } 2 . Submission (26577783) is not visible to me. Can you share code via other methods? 3 . BigIntegers classes typically contain modulo operation.
•  » » » Sorry, here's another submission 24552744There's also efficient long long multiplication in there.
 » Here's the result of running the code below in Custom test on Codeforces: Code#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef double dd; template struct Modular { int value; static const int MOD_value = MOD; Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;} Modular(long long a, long long b) : value(0){ *this += a; *this /= b;} Modular& operator+=(Modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;} Modular& operator-=(Modular const& b) {value -= b.value; if (value < 0) value += MOD;return *this;} Modular& operator*=(Modular const& b) {value = (long long)value * b.value % MOD;return *this;} friend Modular mexp(Modular a, long long e) { Modular res = 1; while (e) { if (e&1) res *= a; a *= a; e >>= 1; } return res; } friend Modular inverse(Modular a) { return mexp(a, MOD - 2); } Modular& operator/=(Modular const& b) { return *this *= inverse(b); } friend Modular operator+(Modular a, Modular const b) { return a += b; } friend Modular operator-(Modular a, Modular const b) { return a -= b; } friend Modular operator-(Modular const a) { return 0 - a; } friend Modular operator*(Modular a, Modular const b) { return a *= b; } friend Modular operator/(Modular a, Modular const b) { return a /= b; } friend std::ostream& operator<<(std::ostream& os, Modular const& a) {return os << a.value;} friend bool operator==(Modular const& a, Modular const& b) {return a.value == b.value;} friend bool operator!=(Modular const& a, Modular const& b) {return a.value != b.value;} }; int32_t main(void){ const int MOD=998244353, NN=2e8; auto tStart = chrono::system_clock::now(); Modular<998244353> a=2, b=3; for(int i=0;i(_diff).count()<<" ms.\n"; tStart = chrono::system_clock::now(); int aa=2, bb=3; for(int i=0;i(_diff).count()<<" ms.\n"; return 0; } The results (2e8 iterations) are: Execution time (w/ class): 2338.19 ms. Execution time (w/o class): 2797.18 ms. ===== Used: 5116 ms, 0 KB