做网站广告联盟赚钱,做微信的微网站,wordpress邮件有<>,成都电商网站开发公司2018/7/14#xff1a;普通的纪中一天
儿子兄弟表示法
将一颗多叉树转换为二叉树的方法#xff0c;左子节点连原树的第一个儿子#xff0c;右子节点连原树的右边的兄弟 适用范围#xff1a;树形dp
数位dp常见方法 状态压缩 分类讨论记忆法#xff08;记忆化搜索#x…2018/7/14普通的纪中一天
儿子兄弟表示法
将一颗多叉树转换为二叉树的方法左子节点连原树的第一个儿子右子节点连原树的右边的兄弟 适用范围树形dp
数位dp常见方法 状态压缩 分类讨论记忆法记忆化搜索
手推exgcd
axbygcd(a,b)axbygcd(a,b)axbygcd(a,b) bx′(a%b)y′gcd(b,a%b)bx#x27;(a\%b)y#x27;gcd(b,a\%b)bx′(a%b)y′gcd(b,a%b) 展开(a%b)(a\%b)(a%b) bx′(a−⌊a/b⌋b)y′gcd(b,a%b)bx#x27;(a-\lfloor a/b\rfloor b)y#x27;gcd(b,a\%b)bx′(a−⌊a/b⌋b)y′gcd(b,a%b) 拆开括号 bx′ay′−⌊a/b⌋by′gcd(b,a%b)bx#x27;ay#x27;-\lfloor a/b\rfloor by#x27;gcd(b,a\%b)bx′ay′−⌊a/b⌋by′gcd(b,a%b) 将aaa和bbb取出 ay′b(x′−⌊a/b⌋y′)gcd(b,a%b)ay#x27;b(x#x27;-\lfloor a/b\rfloor y#x27;)gcd(b,a\%b)ay′b(x′−⌊a/b⌋y′)gcd(b,a%b) ∵gcd(a,b)gcd(b,a%b)\because gcd(a,b)gcd(b,a\%b)∵gcd(a,b)gcd(b,a%b) ∴ay′b(x′−⌊a/b⌋y′)axby\therefore ay#x27;b(x#x27;-\lfloor a/b\rfloor y#x27;)axby∴ay′b(x′−⌊a/b⌋y′)axby 将两边的aaa和bbb取出 y′(x′−⌊a/b⌋y′)xyy#x27;(x#x27;-\lfloor a/b \rfloor y#x27;)xyy′(x′−⌊a/b⌋y′)xy 然后由于两边是等价的 ∴{xy′y(x′−⌊a/b⌋y′)\therefore \left\{\begin{matrix} xy#x27; \\ y(x#x27;-\lfloor a/b \rfloor y#x27;) \end{matrix}\right. ∴{xy′y(x′−⌊a/b⌋y′) 2018/7/16腐败普通的纪中一天
gcd证明
我们设dgcd(a,b)我们设dgcd(a,b)我们设dgcd(a,b) ∵d∣a,d∣b\because d\mid a,d\mid b∵d∣a,d∣b ∴d∣a%b\therefore d\mid a\%b∴d∣a%b 设gcd(b,a%b)d′设gcd(b,a\%b)d#x27;设gcd(b,a%b)d′ ∵d′∣b,d′∣a%b\because d#x27;\mid b,d#x27;\mid a\%b∵d′∣b,d′∣a%b ∴d′∣a\therefore d#x27;\mid a∴d′∣a gcd(a,b)gcd(b,a%b)gcd(a,b)gcd(b,a\%b)gcd(a,b)gcd(b,a%b) 2018/7/17颓废普通的纪中一天
时间复杂的与数据范围
n⩽15O(2n)n\leqslant 15\ \ \ \ \ \ O(2^n)n⩽15 O(2n) n⩽70O(n4)n\leqslant 70\ \ \ \ \ \ O(n^4)n⩽70 O(n4) n⩽500O(n3)n\leqslant 500\ \ \ \ \ \ O(n^3)n⩽500 O(n3) n⩽5000O(n2)n\leqslant 5000\ \ \ \ \ \ O(n^2)n⩽5000 O(n2) n⩽104O(nn)n\leqslant 10^4\ \ \ \ \ \ O(n\sqrt n)n⩽104 O(nn) n⩽105O(n(logn)2)n\leqslant 10^5\ \ \ \ \ \ O(n\ \ (log\ n)^2)n⩽105 O(n (log n)2) n⩽5∗105O(nlogn)n\leqslant 5*10^5\ \ \ \ \ \ O(n\ \ log\ n)n⩽5∗105 O(n log n) n⩽106O(nloglogn)n\leqslant 10^6\ \ \ \ \ \ O(n\ \ log\ log\ n)n⩽106 O(n log log n) n⩽5∗106O(n)n\leqslant 5*10^6\ \ \ \ \ \ O(n)n⩽5∗106 O(n) n⩽2147483647O(n)n\leqslant 2147483647\ \ \ \ \ \ O(\sqrt n)n⩽2147483647 O(n) n⩽max_longlongO(logn)n\leqslant max\_longlong\ \ \ \ \ \ O(log\ n)n⩽max_longlong O(log n) 2018/7/18罕见正常的纪中一天
gcd的和之一
∑i1ngcd(n,i)\sum_{i1}^n gcd(n,i)i1∑ngcd(n,i) ∑d∣nφ(n/d)×d\sum_{d|n} \varphi(n/d)\times dd∣n∑φ(n/d)×d 证明与例题https://blog.csdn.net/mr_wuyongcong/article/details/81104903
