ACM组合数学知识.pptx

ACM组合数学知识 我的一些总结目录 基本组合计数 容斥原理 置换群 Polya定理基本组合计数 加法原理 设事件 A有 m种选取方式，事件 B有 n种选取方式，则选 A或 B共有 m+n种选取方式 . 乘法原理 设事件 A有 m种选取方式，事件 B有 n种选取方式，那么选取 A以后再选取 B共有 m*n种方式 .基本组合计数 排列问题 n个不同物品中选取 r个进行排列的方案数。记 组合问题 n个不同物品中选取 r个的方案数。记组合数恒等式组合数的计算 预处理组合数 O(n2) 预处理排列 O(n) 直接求 O(m)大组合数取模 (*)n,m为大数 ,p=105,p为质数Lucas定理 C(n,m)%p的值等于将 n,m化为 p进制数后，各对应数对的组合数的连乘积 %p。Lucas定理大组合数取模 (*)问题转化为：