CSP-S复习计划-数论

Lucas卢卡斯定理

    \[C(n,m)\% p=C(n/p,m/p)*C(n\% p,m\% p)\% p\]

仅适用于模数为素数时

能Mod的直接Mod,不能Mod的死算,期间可能用到费马小定理

费马小定理

    \[a^(p-1)≡1(mod p) \rightarrow x/a=x*(a^(p-2))(mod p)\]

除以一个数等于乘以这个数的

    \[P-2\]

次方
然后结合费马小定理就可以暴力求组合数,然后lucas快速求组合数

Catalan卡特兰数

    \[h(n)=h(n-1) * 2 * (2*n-1)/(n+1)\]

    \[h(n)=C(2n,n)/(n+1)\]

用于计算括号匹配出栈次数凸多边形三角划分给定节点组成二叉搜索树
只有递推式子没有简便公式

Fibonacci数列

    \[f(n)=f(n-1)+f(n-2)\]

虽然数学不应该这样写,但是~我喜欢~
快速推导有矩阵乘法的方式,就是要推一个转移矩阵

发表评论

电子邮件地址不会被公开。 必填项已用*标注