该模板为作者原创.

问题引入

请输出对 \(p\) 取模后的结果.

请输出模 \(p\) 意义下的结果.

最终答案可以表示为 \(a/b\), 请输出 \(a\cdot b^{-1}\bmod p\), 其中 \(b^{-1}\) 是 \(b\) 对模 \(p\) 的乘法逆元.

在我们做题的时候, 经常会遇到输出在模 \(p\) 意义下的结果的题目. 上面三种是经典的这种要求的说法.

传统做法

这种题目在计算的过程中, 需要用到大量的取模运算. 原则上, 每进行一次加减乘除的运算, 都需要进行至少一次取模. 在读入一个变量后, 也应该立即进行至少一次取模. 如果结果产生了负数, 则可能需要再进行一次取模来避免这种情况的发生. 例如:

计算 \((a+b)\bmod p\). \(-2^{63}<a,b<2^{63}\), \(1<p<2^{62}\).

1
2
3
4
5
6
7
8
9
#include<stdio.h>
typedef long long ll;
int main()
{
    ll a, b, p;
    scanf("%lld%lld%lld", &a, &b, &p);
    printf("%lld", ((a % p + b % p) % p + p) % p);
    return 0;
}

注意到, 这个简单的程序进行了 4 次了取模. 这样产生了一些问题:

在这个程序中, 每一步取模都是缺一不可的. 对 \(a,b\) 的取模是防止 \(a+b\) 过大; 对和取模是题目要求; 最后对取模后的结果在加上一个 \(p\) 后取模是为了防止直接取模得到负数. 上述四个取模缺少任意一个没有替代品的取模, 都会导致答案的错误. 而在做题的过程中, 上述的取模运算或替代品都是机械化而重复的, 有代码复用的可能; 同时, 这些运算缺一不可, 而在赛场考场上做题时, 在大面积的取模过程中, 可能一时疏忽漏掉某个取模, 导致算法正确的程序出现 Wrong Answer 的情况, 这种错误又很难查验, 因此高效便捷的代码复用很有必要.

而且, 取模运算速度较慢, 应该减少模运算的使用: 在某些情况下利用 if-else 结构或三目运算符 ?: 来作为直接偷懒使用取模符号的替代品. 然而, 这些替代品虽然增加了效率, 但是却让代码更加反直觉, 编写更为复杂, 大量重复出现不利于赛场考场的应用. 代码复用就可以令这些问题迎刃而解.

代码实现

题面固定模数 \(p\) 情况的实现, 这也是最常见的一种情况.

如果 \(p\) 是通过键盘输入, 且对于一组数据, 输入后不再改变, 则只需将类声明中的 static const int 类型的常量的声明作为全程序的全局变量即可. 但是对变量取模会显著地比对常量取模更慢.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; ++i)
typedef long long ll;
class llp
{
    int v;
    template <class T>
    llp(T a, int) { v = a; }

public:
    static const int p = 998244353;
    static const int phi = p - 1;
    static const int invp = phi - 1;
    llp() { v = 0; }
    template <class T>
    static T mod(T a) { return a %= p, a >= 0 ? a : a + p; }
    template <class T>
    static T &opmod(T &a) { return a = mod(a); }
    template <class T>
    llp(T a) { v = mod(a); }
    template <class T>
    explicit operator T() const { return v; }
    int operator*() const { return v; }
    int *operator&() const { return (int *)&v; }
    friend istream &operator>>(istream &ipt, llp &x) { return ipt >> x.v, opmod(x.v), ipt; }
    friend ostream &operator<<(ostream &opt, llp x) { return opt << x.v; }
    llp operator+(llp b) const { return v + b.v >= p ? llp(v + b.v - p, 0) : llp(v + b.v, 0); }
    friend llp operator+(ll a, llp b) { return b + a; }
    llp &operator+=(llp b) { return v += b.v, v = v >= p ? v - p : v, *this; }
    llp &operator++() { return *this += 1; }
    llp operator++(int) { return ++*this, *this - 1; }
    llp operator-() const { return v ? llp(p - v, 0) : llp(); }
    llp operator-(llp b) const { return *this + (-b); }
    friend llp operator-(ll a, llp b) { return -b + a; }
    llp &operator-=(llp b) { return *this += -b; }
    llp &operator--() { return *this -= 1; }
    llp operator--(int) { return --*this, *this + 1; }
    llp operator*(llp b) const { return ll(v) * b.v; }
    friend llp operator*(ll a, llp b) { return b * a; }
    llp &operator*=(llp b) { return *this = *this * b; }
    llp operator[](ll b) const
    {
        llp ans = 1, a = *this;
        while (b)
        {
            if (b & 1)
                ans *= a;
            a *= a, b >>= 1;
        }
        return ans;
    }
    llp operator^(ll b) const { return (*this)[b]; }
    llp &operator^=(ll b) { return *this = *this ^ b; }
    llp operator~() const { return *this ^ invp; }
    llp operator/(llp b) const { return *this * ~b; }
    friend llp operator/(ll a, llp b) { return (~b) * a; }
    llp &operator/=(llp b) { return *this = *this / b; }
    llp operator<<(int b) const { return *this * llp(2)[b]; }
    llp &operator<<=(int b) { return *this = *this << b; }
    llp operator>>(int b) const { return *this / llp(2)[b]; }
    llp &operator>>=(int b) { return *this = *this >> b; }
    bool operator==(ll b) const { return mod(b) == v; }
    bool operator==(llp b) const { return v == b.v; }
    bool operator!=(ll b) const { return !(*this == b); }
    bool operator!=(llp b) const { return !(*this == b); }
    bool operator<(llp b) const { return v < b.v; }
    bool operator<=(llp b) const { return v <= b.v; }
    bool operator>(llp b) const { return v > b.v; }
    bool operator>=(llp b) const { return v >= b.v; }
    friend llp operator<(ll a, llp b) { return b > a; }
    friend llp operator<=(ll a, llp b) { return b >= a; }
    friend llp operator>(ll a, llp b) { return b < a; }
    friend llp operator>=(ll a, llp b) { return b <= a; }
    int var() const { return v; }
    int mod() const { return p; }
    llp sqd() const { return *this * *this; }
    llp inv() const { return ~*this; }
    llp pow(ll b) const { return *this ^ b; }
};