为了熟悉各类算法原理,在这里整理一下一些需要经常练习的算法。
扩展欧几里得ex_gcd(求解ax + by = gcd(a, b) (mod p))
P1082 [NOIP2012 提高组] 同余方程 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
P1516 青蛙的约会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
用于计算\(ax + by = c(mod p)\)的最小正整数解,如果\(c\)不是\(gcd(a, b)\)的倍数则无解。
void ex_gcd(int a,int b,int &d,int &x,int &y) { if(!b)d = a, x = 1, y = 0; else ex_gcd(b, a % b, d, y, x), y -= x * (a / b); }
记住ax = 1就可以记住d = a, x = 1, y = 0,记住b和a辗转相除,x, y换位置。
经常用于\(p = b\)的情况下求解,记得将x扩大c/d倍(x = x * c / d),因为用ex_gcd算出的x是在右侧等于gcd(a, b)的结果。
在算出x之后要使得x在modp意义下,所以需要对x取模加p再取模。
int d = 0, x = 0, y = 0; ex_gcd(a, b, d, x, y); if(p % d == 0)p /= d; x = x * c / d; x = (x % p + p) % p;
五行经典代码绝不出错。
主席树(类似树状数组,带前缀和的树)
P1972 [SDOI2009] HH的项链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
P3834 【模板】可持久化线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
注意区间是[0, N]还是[1, N],root[i]表示第i个版本的根,插入函数要牢记,插入、查询函数记得判断x大小切掉一半的递归,确保每次只往一个方向递归。
主席树可以维护一个区间内的第k大的值,也可以维护区间数字的种类数。
树状数组(区间修改,区间查询)
P3368 【模板】树状数组 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
区间修改的树状数组用到了差分的思想,设差分数组为d,我们知道\(a[i] = \sum_{1}^{i}d[i]\),利用这个特性,可以知道\(\sum_{i = 1}^{N}a[i] = \sum_{i = 1}^{N}\sum_{j = 1}^{i}d[i]\),这个式子展开后容易发现\(\sum_{1}^{k}a[i] = \sum_{i = 1}^{k}k * d[i] - (i - 1)d[i]\),所以我们只需要维护一个\(d[i]\)和\((i - 1)d[i]\)即可,或者是\(d[i]\)和\(id[i]\)也可以。这里的k是随着查询而变化的,而i在修改的时候是不变的。
void add(int k,int x){for(int i = k;i <= N; i += lowbit(i))d[i] += x, di[i] += k * x;} int getsum(int k) { int res = 0; for(int i = k;i > 0; i -= lowbit(i))res += (k + 1) * d[i] - di[i]; return res; }
狠狠记住。
Comments NOTHING