jijidawang
jijidawang
全部文章
未归档
题解(1)
归档
标签
去牛客网
登录
/
注册
jijidawang的博客
全部文章
/ 未归档
(共35篇)
乘法逆元
前置芝士: 同余 普通逆元 逆元是模意义下的除法。 就是求解同余方程 \(ax\equiv 1\pmod m\)。 用 exgcd 求解即可。 Code: #include<iostream> #include<cstdio> using namesp...
2020-05-09
0
311
浅谈二维前缀和
首先要了解一个叫做前缀和的东西。 二维前缀和其实就是将普通前缀和加了一维。 也就是可以求一个矩阵内任意子矩阵元素和。 仿照一维前缀和,转移方程如下: \[sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+a_{i,j} \] 这个转移方...
2020-05-09
0
323
浅谈位运算
目录 位运算前言 位运算应用 1 快速幂 2 最大公约数 3 xor 一些应用 4 其他 位运算前言 程序中所有东西在计算机中都是以二进制储存的。 位运算可以直接操作这些二进制。 所以位运算相对于普通运算要快。 这些是所有位...
2020-05-09
0
314
浅谈 Lucas 定理
Lucas 定理是用来求 \(C^n_m\mod p\) 的。 定理 \[C^n_m\equiv C^{n\bmod p}_{m\bmod p}\times C^{n/p}_{m/p}\pmod p \] 证明 由二项式定理得 \(C_a^b\) 为 \((1+x)^a\) 中 \(...
2020-05-09
0
261
浅谈 exgcd
众所周知欧几里得算法是: \[\gcd(a,b)=\gcd(b,a\bmod \,b) \] 也叫辗转相除法。 拓展欧几里得算法(exgcd),可以用来找到形如 \(ax+by=\gcd(a,b)\) 的方程的一组特解。 由裴蜀定理知,原方程一定有解。 我们利用辗转相除法(普通欧几...
2020-05-08
0
366
【洛谷P1754 球迷购票问题】题解
传送门 卡特兰数经典 \(\texttt{AB}\) 分拆问题。 分析: 题意相当于排列 \(n\) 个 \(\texttt A\) 和 \(n\) 个 \(\texttt B\),使得相邻 \(\texttt{AB}\)(有序!)消掉,然后左右元素并到一起再消,最后消完的序...
题解
dp
洛谷
2020-05-08
0
324
浅谈前缀和
引入 如果你想维护一个数据结构,有一个序列 \(a\),每次查询 \(l\sim r\) 区间和(求 \(\sum\limits_{i=l}^ra_i\)),只有查询,线段树&树状数组难免有些大材小用,但是维护它效率要高,甚至要达到 \(\mathcal{O}(1)\)。 这个东西该怎么...
2020-05-03
0
251
浅谈 LCA
LCA(Least Common Ancestors),最近公共祖先,定义为两节点最近的公共祖先好像是废话 前置芝士: 图论 此文章中均设 \(\mathrm{fa}_i\) 为 \(i\) 的父亲,\(\mathrm{dep}_i\) 为 \(i\) 的深度。 暴力 显然我...
2020-05-03
0
237
浅谈Meet in the middle——MITM
目测观看人数 \(0+0+0=0\) \(\mathrm{Meet\;in\;the\;middle}\)(简称 \(\rm MITM\)),顾名思义就是在中间相遇。 可以理解为就是起点跑搜索树基本一半的状态,终点也跑搜索树基本一半的状态,最后撞到中间,一种类似双向 DFS 的东西...
2020-04-20
0
460
拓扑排序
介绍 拓扑排序,对于一个 DAG,每次去掉入度为 \(0\) 的边,最后将图去光,就是拓扑排序。 拓扑排序可以处理一些有序东西,比如在日常工作中,可能会将项目拆分成 \(A,B,C,D\) 四个子部分来完成,但 \(A\) 依赖于 \(B\) 和 \(D\),\(C\) 依赖于 \(D\)(有先...
2020-04-17
0
400
首页
上一页
1
2
3
4
下一页
末页