exCRT
- 求解韩信点兵问题，常见的就是合并不同\(mod\)。
- 先mo一发高神的板子
for(R i=2;i<=n;++i){ ll Y1,Yi,lcm=Lcm(p[i],p[1]); exgcd(p[1],p[i],a[i]-a[1],Y1,Yi); add(a[1],mul(p[1],Y1,lcm),lcm),p[1]=lcm;} - 思想是合并方程组，现在假设我们要求解的是：\[x-p_0*y_0=a_0\]\[x-p_i*y_i=a_i\]
- \(x\)是实际的值，显然有：\[p_0*y_0-p_i*y_i=a_i-a_0\]
- 是\(exgcd\)的形式，把\(y_0\)和\(y_i\)解出来。
- 此时\[p_0*y_0 = a_i-a_0\ \ \ mod \ p_i\]
- 所以让\(y_0\)对\(p_i\)取模，回代到\[x=p_0*y_0+a_0\]
- 此时\(x\)是在\(mod\ p_i*p_0\)意义下，取模后便是新的\(a_0\)了。
最后更新\(p_0\)
- excrt就是把\(p_0*=p_i\)改成\(p_0=lcm(p_0,p_i)\)罢了。
BSGS
拔山盖世？求
\[y^x≡z\ mod\ p\]
设\(x=i*m-j\)，其中\(m=\sqrt p+1\)则
\[y^j*z≡y^{i*m}\]
- 枚举\(j\)，把对应的\(y^j*z\)放在\(hash\)表里。或者也可以用\(map\)
- 注意这个时候的\(j\)要取最大值，从小往大枚举直接附值即可。
- 枚举\(i\)，查对应的\(y^{i*m}\)，如果有值，答案就是\(i*m-j\)了。
- 复杂度\(O(\sqrt p)\)
- 注意前提条件\(gcd(y, p) = 1\)
如果\(y\ mod\ p==0\)，则无解。
- \(upd\ on\ 11.7\)
- 首先有个模板题
注意到
\[y^j*z≡y^{i*m}\]
这个东西中\(i*m-j\ge 0\)恒成立，所以在预处理时要\(j\)要从\(0\)开始到\(m\)，但是查表的时候\(i\)要从\(1\)开始到\(m\)。
同余最短路
- 用一些数去拼凑出给定的数。
- 以最小值建立剩余系，令\(f_i\)表示在拼凑出长度\(mod\)最小值为\(i\)的最小花费。
- 显然每一个\(f_i\)都是这个剩余系中的最小值，且相互独立。
- 连边后做最短路即可。
- 不能拼凑出的最大值即位\(max(f_i-w_0)\)，\(w_0\)是剩余系模数。
- [x]
- 给出四个点1，2，3，4，1和2，2和3，3和4，4和1之间有路相连，现在从2点出发，最后回到2点，要求路径大于等于\(K\)，问路径长度最短是多少，\(K\leq 10^{18},d\leq 3*10^4\)。
- 同余最短路套路了，取一条与\(2\)相连的权值最小的边\(w\)。
- 若存在一条从起点到终点的长度为k的路径，那么必然存在一条长度为\(k+2w\)的路径。
- 即只要一开始在那条边上往返走就好了。
- 设\(d_{i,j}\)表示从起点到\(i\)，路径长度模\(2w\)为\(j\)时，路径长度的最小值。
然后\(dij\)预处理\(d\)，最后枚举所有剩余系，如果大于等于\(K\)就恰好更新答案，否则补上剩下除以\(2*w\)向上取整数。
exgcd
- 求解\(a*x+b*y=c\)的最小特解。
- 注意在某些题目中要判断是否有解（裴蜀定理）。
设\(f=gcd(a,b,c)\)，有一些题目中\(x=0\)要还原成\(b\)，但是此时应该要还原成\(\frac {b}{gcd}\)，这样才能保证最小正整解。
卢卡斯定理
- 处理计算组合时取模数特别小的时候，往往小于\(n,m\)。
对于质数而言，
\[C_n^m=C_{n\ mod\ p}^{m\ mod\ p }*C_{n/p}^{m/p }\]裴蜀定理
\(a*x+b*y=c\)成立的充要条件是\(gcd(a,b)|c\).
组合计数
这不是计数里面的东西吗咕咕。线性筛逆元
- 假设现在要求\(inv_i\)，那么
- 有\(x*i+j=p\)，此时\(j=p\ mod\ i\)，\(x=\frac {p}{i}\)
- 在\(p\)剩余系下，那么\(inv_i=-1*x*inv_j\)
所以\(inv(i)=-inv(p\ mod\ i)*(p/i)\)
三分法
咕咕。
高斯消元
- 我采用的是高斯约旦消元法。
- 先找到系数最大的点提到当前行，然后消为\(1\)，在把其他所有行的这一列消为\(0\)。
- 这样就省去了回带的过程。
- 无解情况：所有系数全为0但是值不为0
- 不唯一解情况：所有系数全为0值也为0
注意要先判断无解再判断解不唯一。