模意义（同余）
同余为数论中的重要概念：
一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余。
记作:
a
≡
b
(
m
o
d
m
)
a≡b(mod m)
a≡b(modm)或者说
a
%
m
=
b
a\%m = b
a%m=b 。
其中 %就是取模运算符；
对模m同余是整数的一个等价关系。
同余有很多奇妙的性质和玩法（）
首先我们约定：大写字母如
A
≡
a
(
m
o
d
p
)
A ≡ a(mod p)
A≡a(modp)
乘法：
若：AB = C ， 则ab %p= c%p
乘法在模意义下同余仍成立；
A = k 1 ∗ p + a ; A = k1 * p +a; A=k1∗p+a;
B = k 2 ∗ p + b ; B = k2 * p +b; B=k2∗p+b;
C = k 1 ∗ k 2 ∗ p ∗ p + ( a ∗ k 2 + b ∗ k 1 ) ∗ p + a ∗ b C = k1*k2*p*p +(a*k2+b*k1)*p + a*b C=k1∗k2∗p∗p+(a∗k2+b∗k1)∗p+a∗b
加减法同理，手推即可发现仍然不影响同余
除法
在除法中要引进一个定理：
费马小定理：结论为： a P − 1 ≡ 1 ( m o d P ) a^{P-1} ≡ 1 (mod P) aP−1≡1(modP)
即a的p-1次方对模P意义下与1同余；
那么显然 a P − 2 a^{P-2} aP−2就可以看成模意义下的1/a;因为 a ∗ a − 1 = 1 a*a^{-1} = 1 a∗a−1=1;
至此，引入一个方便计算a^b的算法，叫做快速幂，是一个简单实用的 l o g 2 ∗ b log_{2}*{b} log2∗b 次乘法时间内就能求出来a^b的算法
这是快速幂的解释代码：https://paste.ubuntu.com/p/zJTMWytKFb/
那现在我们要计算b/a在模P意义下等于何数值，显然需要求 b ∗ a P − 2 % P b*a^{P-2}\%P b∗aP−2%P
就能把除法成功变成乘法
这里只说明同余意义下的加减乘除。还有开根号等各种运算都能在模意义下找到解释；
累加累乘，表达式的化简
∑
\sum
∑这是累加符号
∏
\prod
∏这是累乘符号
[
]
[]
[]这个在式子中出现表示的含义是方括号内容为真，这[**] = 1,否者为假，可以认为是一个真值判别符号；
∣
|
∣这个是整除符号，a|b说明b/a的结果是整数;例如：2|8 , 3|9
A
n
=
2
n
+
3
;
A_n = 2n+3;
An=2n+3;
那么数列A的前n项和
S
n
S_n
Sn =
∑
i
=
1
n
i
∗
2
+
1
\sum_{i=1}^{n}i*2+1
∑i=1ni∗2+1
那么n的阶乘
n
!
=
∏
i
=
1
n
i
n! = \prod_{i=1}^ni
n!=∏i=1ni
面对一些表达式，我们看起来要枚举两个数各自从1到n，时间复杂度为n方，但是其实式子化简之后就会变得很简单：以下的n都是1e5:
1
∑
i
=
1
n
∑
j
=
1
n
∑
k
=
1
n
i
∗
j
∗
k
\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n} i*j*k
∑i=1n∑j=1n∑k=1ni∗j∗k
这个式子乍一看是枚举三个元素，求元素之积，只需要固定ij，思考k的变化：显然是ij+ij2+ij3，这是一个等差数列，于是我们快快乐乐地把式子变成：
∑
i
=
1
n
∑
j
=
1
n
i
∗
j
∗
(
n
+
1
)
∗
n
2
\sum_{i=1}^{n}\sum_{j=1}^{n} i*j*\frac{(n+1)*n}{2}
∑i=1n∑j=1ni∗j∗2(n+1)∗n
一看固定i，j的变化也是等差数列，最后i也是等差数列，上面的式子继续化成：
(
(
n
+
1
)
∗
n
2
)
3
(\frac{(n+1)*n}{2})^3
(2(n+1)∗n)3