信息奥赛中的数学方法_第1页
信息奥赛中的数学方法_第2页
信息奥赛中的数学方法_第3页
信息奥赛中的数学方法_第4页
信息奥赛中的数学方法_第5页
已阅读5页，还剩69页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、信息学竞赛中的数学方法清华大学计算机系 胡泽聪目录l 基础数论l模意义下的运算l费马小定理、欧拉定理与乘法逆元l快速幂与快速乘法l辗转相除法与高精度GCDl线性同余方程与拓展欧几里得算法l筛法与质因数分解l 组合数学入门l排列与组合l常用公式l简单的组合数取模l常用数列l容斥原理与禁位排列l 位运算及bitset基础数论BASIC NUMBER THEORY基本概念带余除法模数、取模同余因子互质最大公因数模意义下的运算 很多题目的基础 加减乘法在模意义下封闭 除法则不同费马小定理欧拉定理乘法逆元一些大质数快速幂快速幂快速幂：代码快速乘法最大公因数（GCD）更相减损术辗转相除法辗转相除法：代码高

2、精度加减乘法高精度除法高精度GCD线性同余方程拓展欧几里得算法拓展欧几里得算法拓展欧几里得算法拓展欧几里得算法：代码求解线性同余方程分解质因数枚举因子筛法筛法基础数论：例题BASIC NUMBER THEORY: EXAMPLESNOIP2012 D2T1同余方程题面题解 拓展欧几里得的直接应用。 也可以直接算逆元。POJ1061青蛙的约会题面题解HDU2824The Euler Function题意题解POJ2480Longges Problem题意题解SGU106The Equation题意题解进一步了解组合数学入门INTRODUCTORY COMBINATORICS基本计数原理加法原理乘

3、法原理减法原理计数问题 统计满足某些条件的物体的个数。 例：求项链的本质不同的染色方案数求图的不同生成树的个数 答案通常很大，需要取模输出。 两个要点： 不重、不漏排列与组合Pascal公式常用公式常用公式常用公式证明的两种方式1. 组合学推理2. 数学推导尝试一下证明模意义下的组合数Catalan数列Catalan数列Bell数列容斥原理错位排列禁位排列组合数学入门：例题INTRODUCTORY COMBINATORICS: EXAMPLES一道数学题题面题解POJ3421X-factor Chains题意题解URAL1860Fiborial题面题解POJ3088Push Button Lo

4、ck题面题解无名试题1题面题解组合数学习题8.5题面题解SKI题面题解进一步了解位运算与bitsetBITWISE OPERATIONS AND STD:BITSET位运算集合的二进制表示 适用于全集大小比较小（通常在32以内）的情况。 用一个unsigned int表示一个子集。 二进制位为1代表子集中有这个元素，0代表没有。判断元素是否存在：加入元素：删除元素：改变元素状态：（如果存在则删除，否则加入）与其他集合的交并异或集合的补：与其他集合的差：集合操作枚举子集std:bitsetstd:bitset用例自己实现bitset 内部为unsigned int数组。 与或非异或：对所有数字进行位运算 左移右移：自己实现bitsetbitset的简单应用 状态压缩动态规划（通常

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论