[tju]组合计数_080709(ACM)

null组合计数问题组合计数问题何亮 roba269@gmail.com基础知识基础知识加法原理 乘法原理 排列 组合 组合数递推式 在很多复杂问题中可以预处理出 在要求 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 mod某数时常用可重排列组合可重排列组合可重排列 比如求{a,a,b,b,c}的不同全排列数： 5! / (2! * 2!) 可重组合 给定n种物品，要求取出m个(可以重复取) 容斥原理容斥原理Inclusion-Exclusion Principle 容斥原理容斥原理容斥原理的应用1——欧拉函数 定义phi(p)为比p小的与p互素的数 比如, phi(3)=2, phi(6)=2 设n的素因子有p1, p2, p3, … pk 欧拉函数欧拉函数包含p1, p2…的个数为n/p1, n/p2… 包含p1*p2, p2*p3…的个数为n/(p1*p2)… 欧拉函数欧拉函数在实际代码中可以用类似素数筛法求出 for (i = 1 ; i < MAXN ; i++) phi[i] = i; for (i = 2 ; i < MAXN ; i++) if (phi[i] == i) { for (j = i ; j < MAXN ; j += i) { phi[j] /= i; phi[j] *= i - 1; } }错位排列错位排列容斥原理应用2——错位排列 若一个1..n的排列{a1,a2,a3…,an}满足a1≠1, a2≠2,…，则称其为一个(全)错位排列 求所有错位排列的个数错位排列错位排列所有排列数n! 有大于1个正确的排列数n*(n-1)! 有大于2个正确的排列数C(n,2)*(n-2)! 故全错的排列数为 错位排列错位排列递推公式 f(n) = (n-1)*(f(n-1)+f(n-2)) 解释： 设把元素a放到位置B，则有两种情况 若元素b放到位置A，则变为f(n-2) 若b放在A,B之外，则变为f(n-1) 元素a可错放的位置有n-1种，故得上式Catalan数Catalan数闭形式 递推式 Catalan数Catalan数1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 有多种解释方式 不穿过对角线的路径数 完全加括号 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 数 满二叉树数目 多边形三角剖分方案数 Catalan数 – 形式1Catalan数 – 形式1不穿过对角线的路径数 一条不合法的路径 对应 一条(0,0)到(n-1,n+1)的路径Catalan数 – 形式1Catalan数 – 形式1全部路径有C(2n,n)条 (0,0)到(n-1,n+1)的路径有C(2n,n-1)条 故合法路径有C(2n,n) - C(2n,n-1)条 化简可得Catalan数 – 形式1Catalan数 – 形式1类似问题有 合法括号序列方案数 排队找零钱问题 出栈顺序问题Catalan数 – 形式2Catalan数 – 形式2 多边形三角 剖分数Catalan数 – 形式2Catalan数 – 形式2任选一边(不妨选边0-1)，设其所在的三角形的顶点为点k，则多边形被分成一个k边形和一个n+1-k边形 定义k=2也为一种合法情况 则有f(n)=sigma(f(k)*f(n+1-k)) (2<=k<=n-1) f(n)=Catalan(n-2)Catalan数 – 形式2Catalan数 – 形式2N个中间结点的满二叉树数为Catalan(n) N个元素完全加括号的方案数为Catalan(n-1)例题例题POJ 3597 Polygon Division 求把一个N边形划分成三角形和四边形的方案数。(3<=N<=5000)例题例题确定一条起始边，分情况考虑 连出三角形——同Catalan数 连出四边形 分使用1/2/3条对角线情况 2条对角线又有相邻与不相邻两种情况 对于使用3条对角线的情况，直接写的复杂度是O(n^3)，可以通过预处理降到O(n^2)Super CatalanSuper Catalan任意加括号的合法方案数 不必完全加括号 UVA 10312 当四个元素时，有11种方案 xxxx, (xx)xx, x(xx)x, xx(xx), (xxx)x, x(xxx), ((xx)x)x, (x(xx))x, (xx)(xx), x((xx)x), x(x(xx)) Super CatalanSuper Catalan容易发现 S(N) = sigma( S(P1)*S(P2)*S(P3)*...*S(Pn) ) for all P1+P2+..+Pn = N 利用生成函数可以得出(过程略): S(n) = (3(2n-3)S(n-1) – (n-3)S(n-2)) / n S(1) = S(2) = 1 详见Brualdi《组合数学》8th chapter第二类Stirling数第二类Stirling数n个可区分的元素划分成k个集合的方案数 如n=4, k=2，则有7种方案 {1,2,3},{4} {1,2,4},{3} {1,3,4},{2} {2,3,4},{1} {1,2},{3,4} {1,3},{2,4} {1,4},{2,3}null第二类Stirling数第二类Stirling数当k=2时有 递推式整数分拆问题整数分拆问题TOJ 1746.   How many sums Ferrers图 & 其共轭图整数分拆问题整数分拆问题求分拆数的dp解法 用dp[i][j] 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示把i分解，且最大的数为j的情况数，则有 dp[i][j] = ∑dp[i-j][k] (for all 0 <= k <= min(j,i-j)) 最后结果为∑dp[n][j] (for all j) O(n^3)…整数分拆问题整数分拆问题O(n^2)解法 用opt[i][j]表示把i拆成j个数(可为0)的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 数，则有如下方程: opt[i][j] = opt[i][j-1] + opt[i-j][j] 边界条件opt[0][j] = 0, opt[0][0] = 1 解释为，要么第j个数为0，这样就是opt[i][j-1]，要么我们可以把所有j个数都减1，于是得到opt[i-j][j]。 例题例题UVA 10313 Pay the Price 要用硬币凑出面值N，[1..N]的每种面值的硬币都无限多，但要求恰好使用k个硬币。L1<=k<=L2，L1,L2,N给定。 N<=300, L1,L2<=1000 如N=6, L1=2, L2=5。答案为9 例题例题容易把此问题转化为，用不超过L枚硬币凑出N的方案数。 直接DP? 用opt[i][j][k]表示用最大值不超过k的j枚硬币组成面值为i的方案数 O(n^3)…时间空间都不够例题例题根据共轭Ferrers图—— 使用k个硬币的方法数 = 最大值为k的方法数! 用opt[i][j]表示最大值不超过j的凑出面值i的方法数，那么有方程 opt[i][j] = opt[i-j][j] + opt[i][j-1] 则最大值恰好为k的方法数为即 opt[i][k] – opt[i][k-1]小结小结盒子装球问题小结—— 第一类Stirling数第一类Stirling数把n个元素划分成k个“循环”的方案数 如当n=4,k=2时，有11种方案 [1,2,3][4] [1,2,4][3] [1,3,4][2] [2,3,4][1] [1,3,2][4] [1,4,2][3] [1,4,3][2] [2,4,3][1] [1,2][3,4] [1,3][2,4] [1,4][2,3]null第一类Stirling数第一类Stirling数根据排列与置换的对应关系有 递推式例题例题Topcoder SRM 391 KeysInBoxes N个箱子里锁着N把钥匙，箱子与钥匙一一对应，你有k个炸弹，每当炸开一个箱子，就可以取出其中的钥匙，再用此钥匙打开更多的箱子。求能打开(及炸开)所有箱子的概率。 如当N=3, k=2时，答案为5/6例题例题每种排列出现的概率为 1/N! 每种排列对应一种置换方式 当某排列的循环节<=k时，才可以打开所有箱子，这个数正是S1{n,k} 故答案即为置换置换一个排列和一个置换相对应 通常用一个2*n的矩阵表示 (1 2 3 4 5 6) (5 6 3 1 2 4) 循环 置换可以看成一个函数，可以进行合成例题例题TOJ 1008.   Cipher 给出置换规则及明文，求经N次加密之后的密文。(N可能很大) Input 10 4 5 3 7 2 8 1 6 10 9 1 Hello Bob 1995 CERC Output BolHeol b C RCE 例题例题给出一条密文，问其是否可能是由明文经某置换算法连续运算两次得到。 考虑奇偶长度置换节的运算结果…… 群群给定一个集合G={a,b,c,…}和集合G上的二元运算，并满足: (a) 封闭性：a,bG, cG, a*b=c。 (b) 结合律：a,b,cG, (a*b)*c=a*(b*c)。 (c) 单位元：eG, aG, a*e=e*a=a。 (d) 逆元：aG, bG, a*b=b*a=e，记b=a-1。 则称集合G在运算*之下是一个群。 置换群置换群如果一个置换的集合Sn及定义于其上的“合成”运算满足群的条件，则称其为置换群。 合成的封闭性 结合律 单位元（恒等置换） 逆元（逆置换）置换群置换群如一个允许旋转的正方形角点有四种置换： (1 2 3 4) (2 3 4 1) (3 4 1 2) (4 1 2 3) 它们构成一个置换群Burnside定理Burnside定理用D(aj) 表示在置换aj下不变的染色方案的个数。L表示本质不同的方案数。则有 以允许旋转的正方形，用两种颜色着色为例Burnside定理Burnside定理对于(1,2,3,4)，所有16种方案都不变 对于(2,3,4,1)和(4,1,2,3)，各有2种方案不变 对于(3,4,1,2)，有{RRRR},{BBBB}, {RBRB},{BRBR}4种方案不变 总的本质不同的着色数有 (16+2+2+4)/4 = 6种Polya定理Polya定理Burnside定理中的D(aj)不易求出 实际上易得到，若可用m种颜色，对于一个置换aj，设它的循环数为c(aj)，则在此置换下不变的着色方案数为mc(aj) 即对不同的循环节分别独立染色 故总的本质不同的方案数为 Polya定理Polya定理如前例： (1,2,3,4)循环数为4 (2,3,4,1), (4,1,2,3)循环数为1 (3,4,1,2)循环数为2 最终答案(24+21+21+22)/4 = 6 例题例题TOJ 1341.   Let it Bead 给定珠子数和颜色数 / 旋转翻转等价 例题例题旋转： 若转过k个珠子，则循环节数为gcd(k,n) 翻转： 若总数为奇，则共有循环节数为(n+1)/2的置换n个 若总数为偶，则有循环节数为n/2的置换n/2个，循环节数为n/2+1的置换n/2个例题例题TOJ 2795 The Queen's New Necklaces 旋转等价 对每种颜色的数目有限制 Sample Input: 2 3 Sample Output: 2例题例题对循环节的 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 类似 同一置换里的循环节都等长(设长度为k) 若要求某染色方案在某置换下不变，则此置换的每个循环节必须染以相同颜色 例题例题若对某长度k，某颜色数a[i]%k!=0，则此长度下不可能保持不变 否则，共有total/k个循环节，依次对每个颜色选出相应个数来填充，则有 最终结果为生成函数生成函数Generating Function, 母函数 简单来说，就是把一个数列(a0,a1,…,an,…)表示成函数的形式G(z) = a0 + a1*z + a2*z2 + … + an*zn + … 生成函数的特点是把一个无穷数列用一个紧凑的形式表示出来，可以方便某些运算 注：在大部分情况下，可以忽略函数的收敛性等(?) 简单举例简单举例用1分,5分,10分的硬币，凑出N分钱 F1(x)=1+x+x2+x3+… F5(x)=1+x5+x10+x15+… F10(x)=1+x10+x20+… 则把F1(x)*F5(x)*F10(x)多项式乘积展开，xN项对应的系数即为所求生成函数常见运算生成函数常见运算两个数列合并: 右移m个数: 左移m个数:生成函数常见运算生成函数常见运算求导 积分 卷积常见数列对应生成函数常见数列对应生成函数 (1,1,1,1,…) G(z) = 1 / (1-z) (1,2,3,4,…) G(z) = 1 / (1-z)2 (1,2,4,8,…) G(z) = 1 / (1-2z) (1,c,c2,c3,…) G(z) = 1 / (1-cz) (0,1,1/2,1/3,1/4,…) G(z) = ln (1 / (1-z)) 常见数列对应生成函数常见数列对应生成函数G(z) = (1+z)cG(z) = 1 / (1-z)c生成函数的展开生成函数的展开Taylor定理：在x=0附近，我们有 可利用此式展开生成函数 生成函数的应用生成函数的应用在求解递归中，作用巨大 例1： 解Fibonacci： F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) 生成函数的应用生成函数的应用定义生成函数 B(x)=F(0)+F(1)x+F(2)x2+F(3)x3+… 即有 所以 null