博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
数学模型
阅读量:5744 次
发布时间:2019-06-18

本文共 3297 字,大约阅读时间需要 10 分钟。

Catalan

Stirling

容斥

  • (状压+容斥)
  • (容斥+递推)

莫比乌斯反演与筛法

\[g(n)=\sum_{d|n}f(d)\] \[f(n)=\sum_{d|n}{\mu(d)g(\frac{n}{d})}\]

blogs:

题目:

  • + +
    三倍经验
  • (莫比乌斯反演+树状数组)
  • (真的毒瘤的预处理啊orz)
  • (关于幂的莫比乌斯反演orz)

二项式反演

\[f(n)=\sum_{k=p}^n (\begin{matrix} n \\ k \end{matrix})g(k)\]

\[g(n)=\sum_{k=p}^n(-1)^{n-k}(\begin{matrix} n \\ k \end{matrix})f(k)\]

中国剩余定理

  • \[ \begin{Bmatrix} x \equiv c_1 (mod\; m_1)\\ x \equiv c_2 (mod\; m_2)\\ \cdots\\ x \equiv c_n (mod\; m_n) \end{Bmatrix} \]
    其中\((m_i, m_j)==1, i\not= j\)
    \(M=\prod_{i=1}^nm_i\)
    \(x=(\sum_{i=1}^nc_i*\frac{M}{m_i}*inv(\frac{M}{m_i}, m_i))mod\;M\)

  • \[ \begin{Bmatrix} x \equiv c_1 (mod\; m_1)\\ x \equiv c_2 (mod\; m_2)\\ \cdots\\ x \equiv c_n (mod\; m_n) \end{Bmatrix} \]
    对于两个方程
    \[x \equiv c_1 (mod\; m_1)\\ x \equiv c_2 (mod\; m_2)\]
    合并为一个,有解条件为\((m_1, m_2)|(c_2-c_1)\)
    \[d=(m_1, m_2), m=\frac{m_1m_2}{d}\\ c=(inv(\frac{m_1}{d}, \frac{m_2}{d})*\frac{c_2-c_1}{d})\% (\frac{m_2}{d})*m_1+c_1\]
    最终\(x=c\%m\)

  • \(C_n^m%p\)
    唯一分解\(p=\prod_{i=1}^qp_i^{k_i}\)
    \[ \begin{Bmatrix} x \equiv C_n^m \%p_1^{k_1} (mod\; p_1^{k_1})\\ x \equiv C_n^m \%p_2^{k_2} (mod\; p_2^{k_2})\\ \cdots\\ x \equiv C_n^m \%p_q^{k_q} (mod\; p_q^{k_q}) \end{Bmatrix} \]
    \(x\)即为答案

公式:

  1. \[g(n)=\sum_{d|n}f(d)\] \[f(n)=\sum_{d|n}{\mu(d)g(\frac{n}{d})}\]
  2. \[f(n)=\sum_{k=p}^n (\begin{matrix} n \\ k \end{matrix})g(k)\]
    \[g(n)=\sum_{k=p}^n(-1)^{n-k}(\begin{matrix} n \\ k \end{matrix})f(k)\]
  3. \[g(n)=\sum_{n|d}{f(d)[d \leq m]}\] \[f(n)=\sum_{n|d}{\mu(\frac{d}{n})g(d)[d \leq m]}\]
  4. 如果\(f(n)\)是积性函数,且\((x, y) = 1\),则有\[f(xy)=f(x)f(y)\]
  5. \[\sum_{i=1}^{n}{i[(i, n) == 1]}= \frac{\varphi(n)*n}2\]
    (用到结论:\(if (i, n) == 1, then (n-i, n) = 1\))
  6. \[(id*\mu)(i)=\varphi(i)\]
    \[(\varphi*I)(i)=id(i)\]
    \[(\mu*I)(i)=e(i)\]
  7. \[[n == 1]=\sum_{d|n}{\mu(d)}\]
  8. \[n=\sum_{d|n}{\varphi(d)}\]
  9. \[\sum_{i=1}^{n}{\sum_{j=1}^{m}ij}=\frac{n^2(n+1)^2}{4}\]
  10. 除数函数 \[\sigma_k(n)=\sum_{d|n}{d^k}\]
    约数个数函数 \[\tau(n)=\sigma_0(n)=\sum_{d|n}1\]
    约数和函数\[\sigma(n)=\sigma_1(n)=\sum_{d|n}d\]
  11. \[\sum_{i=1}^ni=\frac{n(n+1)}{2}\]
    \[\sum_{i=1}^ni^2=\frac{(n+1)(2n+1)n}{6}\]
    \[\sum_{i=1}^ni^3=\frac{n^2(n+1)^2}{4}\]
  12. \[\varphi(ij)=\frac{\varphi(i)\varphi(j)(i,j)}{\varphi((i,j))}\]
  13. \[[f(x) == 1] = e(f(x))=(\mu*I)(f(x))\](常用于引进\(\mu\)以进行莫比乌斯反演,如[NOI2016]循环之美)
  14. \[(\begin{matrix} 0 \\ n \end{matrix})+(\begin{matrix} 1 \\ n \end{matrix})+(\begin{matrix} 2 \\ n \end{matrix})+...+(\begin{matrix} n \\ n \end{matrix})=2^n\]
  15. \[d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x, y) == 1]\]
  16. \[ \begin{Bmatrix} x \equiv c_1 (mod\; m_1)\\ x \equiv c_2 (mod\; m_2)\\ \cdots\\ x \equiv c_n (mod\; m_n) \end{Bmatrix} \]
    其中\((m_i, m_j)==1, i\not= j\)
    \(M=\prod_{i=1}^nm_i\)
    \(x=(\sum_{i=1}^nc_i*\frac{M}{m_i}*inv(\frac{M}{m_i}, m_i))mod\;M\)
  17. \[ \begin{Bmatrix} x \equiv c_1 (mod\; m_1)\\ x \equiv c_2 (mod\; m_2)\\ \cdots\\ x \equiv c_n (mod\; m_n) \end{Bmatrix} \]
    对于两个方程
    \[x \equiv c_1 (mod\; m_1)\\ x \equiv c_2 (mod\; m_2)\]
    合并为一个,有解条件为\((m_1, m_2)|(c_2-c_1)\)
    \[d=(m_1, m_2), m=\frac{m_1m_2}{d}\\ c=(inv(\frac{m_1}{d}, \frac{m_2}{d})*\frac{c_2-c_1}{d})\% (\frac{m_2}{d})*m_1+c_1\]
    最终\(x=c\%m\)
  18. \(C_n^m%p\)
    唯一分解\(p=\prod_{i=1}^qp_i^{k_i}\)
    \[ \begin{Bmatrix} x \equiv C_n^m \%p_1^{k_1} (mod\; p_1^{k_1})\\ x \equiv C_n^m \%p_2^{k_2} (mod\; p_2^{k_2})\\ \cdots\\ x \equiv C_n^m \%p_q^{k_q} (mod\; p_q^{k_q}) \end{Bmatrix} \]
    \(x\)即为答案

转载于:https://www.cnblogs.com/zerolt/p/9281380.html

你可能感兴趣的文章
chm文件打开,有目录无内容
查看>>
whereis、find、which、locate的区别
查看>>
一点不懂到小白的linux系统运维经历分享
查看>>
桌面支持--打不开网页上的pdf附件解决办法(ie-tools-compatibility)
查看>>
nagios监控windows 改了NSclient++默认端口 注意事项
查看>>
干货 | JAVA代码引起的NATIVE野指针问题(上)
查看>>
POI getDataFormat() 格式对照
查看>>
Python 中的进程、线程、协程、同步、异步、回调
查看>>
好的产品原型具有哪些特点?
查看>>
实现java导出文件弹出下载框让用户选择路径
查看>>
刨根问底--技术--jsoup登陆网站
查看>>
OSChina 五一劳动节乱弹 ——女孩子晚上不要出门,发生了这样的事情
查看>>
Spring--通过注解来配置bean
查看>>
pandas 十分钟入门
查看>>
nginx rewrite
查看>>
前端安全系列(一):如何防止XSS攻击?
查看>>
查看Linux并发连接数
查看>>
你是谁不重要,关键是你跟谁!
查看>>
CSS中规则@media的用法
查看>>
pychecker:分析你的python代码
查看>>