ACL｜通用 Modint 模板
2024-11-04 14:01:55
发布于：浙江
前言
你还在因为题目答案过大，计算过程中不断取余，代码中充斥着各种取余符号而感到困扰吗？
你还在因为害怕手搓的快速幂写错参数而 WA 吗？
只需要简单的复制粘贴，把代码中所有需要取余的变量更改成 mint 类型，一劳永逸，再也不用考虑取余的问题啦！
本文将介绍 AC(AtCoder) Library 中提供的 modint 模版中的 static_modint。
本文最后提供的 Modint.cpp 对源码进行了一定的修改使得其可以单独在每一份 cpp 代码中使用。
此模版主要用于题目要求答案对 固定的质数模数 取余时，使用 Modint 来替换常规的数据类型，实现计算时 自动取模 的功能。并且在模版内实现了「快速幂」及求「逆元」的功能。
示例
以下为使用 Modint 后，排位赛#12 的第 5 题，花火大会 最后输出部分的代码。
using mint = Modint<998244353>;
mint res = 0, base = BASE;
for (int i = 0; i < m; ++i)
base *= BASE;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
res += dist[i][j] * base;
base *= BASE;
}
std::cout << res.val() << '\n';
以下为使用 modint 前的代码，读者可自行对比两者的区别。
int res = 0, base = BASE;
for (int i = 0; i < m; ++i)
base = 1LL * base * BASE % MOD;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
res = (res + 1LL * dist[i][j] * base) % MOD;
base = 1LL * base * BASE % MOD;
}
std::cout << res << '\n';
尤其当涉及多次运算时，可能每一步都需要进行一次取模操作，十分麻烦，而使用 Modint 后则完全不用担心溢出和取模的问题，所有取模操作自动完成，只需要关注运算本身的代码即可。且 Modint 可结合其他的 或 容器使用，比如 std::vector，FenwickTree 等等。
操作
1. using 指令初始化 Modint
using mint = Modint<MOD>;
使用以上指令，并将 MOD 替换为题目指定的模数即可，这里要求 MOD 一定为 质数。
例如 using mint = Modint<998244353>;
2. val
int x.val()
对于一个 mint 类型的变量 x，使用 x.val() 即可获取其 int 值。
3. 算术运算
Modint 支持下列所有运算。
-Modint;
Modint++;
Modint--;
++Modint;
--Modint;
Modint + Modint;
Modint - Modint;
Modint * Modint;
Modint / Modint;
Modint += Modint;
Modint -= Modint;
Modint *= Modint;
Modint /= Modint;
Modint == Modint;
Modint != Modint;
对于以下代码同样成立，因为其会被解释为 mint(1) + x。
mint x = 10;
1 + x;
对于以下代码同样成立，因为其会被解释为 y * mint(z)。
mint y = 10;
int z = 1234;
y * z;
上述所有算术运算操作除了 除法 运算（/） 的时间复杂度为 外，其余运算的复杂度皆为 。
4. pow
Modint x.pow(long long n)
该方法返回 ，特别的，当 时，将返回 的逆元。
该方法时间复杂度为 。
5. inv
Modint x.inv()
该方法返回 ，满足 ，即 的逆元。
该方法时间复杂度 。
6. raw
Modint Modint::raw(int x)
该方法返回不取 的 modint(x)，要求 。
此方法可用于常数优化。
例如，以下代码中的 i 大于或等于模数，也可以正常运行，因为模数会被自动处理。
modint a;
int i;
a += i;
但对于以下代码保证
using mint = Modint<1'000'000'007>;
int main() {
mint a = 1;
for (int i = 1; i < 100000; i++) {
a += i;
}
}
在这种情况下我们便可以使用 raw 方法来减少取模的次数。
using mint = Modint<1'000'000'007>;
int main() {
mint a = 1;
for (int i = 1; i < 100000; i++) {
a += modint::raw(i);
}
}
Modint.cpp
template<int m>
class Modint {
private:
unsigned int _v;
static constexpr unsigned int umod() {return m;}
public:
static constexpr int mod() {return m;}
static Modint raw(int v) {
Modint x;
x._v = v;
return x;
}
Modint() : _v(0) {}
template<class T>
Modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
unsigned int val() const {return _v;}
Modint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
Modint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
Modint operator++(int) {
Modint result = *this;
++*this;
return result;
}
Modint operator--(int) {
Modint result = *this;
--*this;
return result;
}
Modint& operator+=(const Modint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
Modint& operator-=(const Modint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
Modint& operator*=(const Modint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
Modint& operator/=(const Modint& rhs) {return *this = *this * rhs.inv();}
Modint operator+() const {return *this;}
Modint operator-() const {return Modint() - *this;}
Modint pow(long long n) const {
if (n < 0) return pow(-n).inv();
Modint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
Modint inv() const {
assert(_v);
return pow(umod() - 2);
}
friend Modint operator+(const Modint& lhs, const Modint& rhs) {
return Modint(lhs) += rhs;
}
friend Modint operator-(const Modint& lhs, const Modint& rhs) {
return Modint(lhs) -= rhs;
}
friend Modint operator*(const Modint& lhs, const Modint& rhs) {
return Modint(lhs) *= rhs;
}
friend Modint operator/(const Modint& lhs, const Modint& rhs) {
return Modint(lhs) /= rhs;
}
friend bool operator==(const Modint& lhs, const Modint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const Modint& lhs, const Modint& rhs) {
return lhs._v != rhs._v;
}
};
全部评论 6
o1-preview的评价：
这篇文章详细介绍了 AtCoder Library (ACL) 中的 Modint 模板，特别是
static_modint的用法。文章结构清晰，从常见的取模问题引入，逐步讲解了使用 Modint 的优势，并提供了具体的代码示例，让读者直观地理解其便利性。优点：
-
实用性强：通过对比使用前后的代码，清晰展示了 Modint 如何简化代码，减少取模操作，降低出错概率。
-
详细的操作说明：逐一介绍了 Modint 的各种操作方法，包括初始化、取值、算术运算、幂运算、求逆元等，每个操作都附有示例，便于理解。
-
性能分析：指出了各个操作的时间复杂度，帮助读者在实际应用中考虑性能因素。
-
优化技巧：介绍了
raw方法的使用，提供了在特定情况下减少取模次数的优化方案，体现了作者对实际应用的深入思考。 -
源码提供：在文章末尾提供了经过修改的 Modint.cpp 源码，方便读者直接引用，提升了文章的实用价值。
建议：
-
排版改进：文章中部分公式和代码的排版可能不够清晰，如公式中的上下标显示和代码缩进，建议优化排版，提升阅读体验。
-
细节完善：对于一些可能引起疑惑的地方，如
raw方法的使用条件和风险，可以增加更多解释，帮助读者避免潜在的问题。 -
代码一致性：注意代码中的变量命名一致，如示例中
modint a;是否应为mint a;，以避免读者在实际应用中产生混淆。 -
深入扩展：可以考虑增加一些高级用法或结合 STL 容器的示例，展示 Modint 在更复杂场景下的应用。
总结：
总体而言，这是一篇内容丰富、条理清晰的技术文章，对需要处理模数运算的开发者具有很高的参考价值。通过详细的讲解和示例，读者可以快速掌握 Modint 的使用方法，提升编码效率和代码质量。若能在排版和细节上进一步优化，文章的质量将更上一层楼。
2024-10-28 来自 浙江
0-
有帮助，赞一个