学习手记(2018/7/14~2018/7/18)

2018/7/14：普通的纪中一天

儿子兄弟表示法

将一颗多叉树转换为二叉树的方法，左子节点连原树的第一个儿子，右子节点连原树的右边的兄弟

适用范围：树形dp

数位dp常见方法

1. 状态压缩

2. 分类讨论
3. 记忆法（记忆化搜索）

手推exgcd

$ax+by=gcd(a,b)$ax+by=gcd(a,b)
$bx'+(a\%b)y'=gcd(b,a\%b)$bx′+(a%b)y′=gcd(b,a%b)
展开$(a\%b)$(a%b)
$bx'+(a-\lfloor a/b\rfloor b)y'=gcd(b,a\%b)$bx′+(a−⌊a/b⌋b)y′=gcd(b,a%b)
拆开括号
$bx'+ay'-\lfloor a/b\rfloor by'=gcd(b,a\%b)$bx′+ay′−⌊a/b⌋by′=gcd(b,a%b)
将$a$a和$b$b取出
$ay'+b(x'-\lfloor a/b\rfloor y')=gcd(b,a\%b)$ay′+b(x′−⌊a/b⌋y′)=gcd(b,a%b)
$\because gcd(a,b)=gcd(b,a\%b)$∵gcd(a,b)=gcd(b,a%b)
$\therefore ay'+b(x'-\lfloor a/b\rfloor y')=ax+by$∴ay′+b(x′−⌊a/b⌋y′)=ax+by
将两边的$a$a和$b$b取出
$y'+(x'-\lfloor a/b \rfloor y')=x+y$y′+(x′−⌊a/b⌋y′)=x+y
然后由于两边是等价的
$\therefore \left\{\begin{matrix} \\ x=y' \\ y=(x'-\lfloor a/b \rfloor y') \\ \\ \end{matrix}\right.$∴⎩⎪⎪⎨⎪⎪⎧​x=y′y=(x′−⌊a/b⌋y′)​

---

2018/7/16：腐败普通的纪中一天

gcd证明

$我们设d=gcd(a,b)$我们设d=gcd(a,b)
$\because d\mid a,d\mid b$∵d∣a,d∣b
$\therefore d\mid a\%b$∴d∣a%b
$设gcd(b,a\%b)=d'$设gcd(b,a%b)=d′
$\because d'\mid b,d'\mid a\%b$∵d′∣b,d′∣a%b
$\therefore d'\mid a$∴d′∣a
$gcd(a,b)=gcd(b,a\%b)$gcd(a,b)=gcd(b,a%b)

---

2018/7/17：颓废普通的纪中一天

时间复杂的与数据范围

$n\leqslant 15\ \ \ ：\ \ \ O(2^n)$n⩽15   ：   O(2n)
$n\leqslant 70\ \ \ ：\ \ \ O(n^4)$n⩽70   ：   O(n4)
$n\leqslant 500\ \ \ ：\ \ \ O(n^3)$n⩽500   ：   O(n3)
$n\leqslant 5000\ \ \ ：\ \ \ O(n^2)$n⩽5000   ：   O(n2)
$n\leqslant 10^4\ \ \ ：\ \ \ O(n\sqrt n)$n⩽104   ：   O(nn​)
$n\leqslant 10^5\ \ \ ：\ \ \ O(n\ \ (log\ n)^2)$n⩽105   ：   O(n  (log n)2)
$n\leqslant 5*10^5\ \ \ ：\ \ \ O(n\ \ log\ n)$n⩽5∗105   ：   O(n  log n)
$n\leqslant 10^6\ \ \ ：\ \ \ O(n\ \ log\ log\ n)$n⩽106   ：   O(n  log log n)
$n\leqslant 5*10^6\ \ \ ：\ \ \ O(n)$n⩽5∗106   ：   O(n)
$n\leqslant 2147483647\ \ \ ：\ \ \ O(\sqrt n)$n⩽2147483647   ：   O(n​)
$n\leqslant max\_longlong\ \ \ ：\ \ \ O(log\ n)$n⩽max_longlong   ：   O(log n)

---

2018/7/18：罕见正常的纪中一天

gcd的和之一

$\sum_{i=1}^n gcd(n,i)$i=1∑n​gcd(n,i)
$=$=
$\sum_{d|n} \varphi(n/d)\times d$d∣n∑​φ(n/d)×d
证明与例题：https://blog.****.net/mr_wuyongcong/article/details/81104903