世界经理人网站手机版,暴雪国服,广西建设工程协会网站,湖南省住房城乡建设厅网站前言
闲的无聊懒得做题不如来水点博客。
虽然一直作为一个感性做题的选手#xff0c;但是理性层面上确实是分析题目初步做法的一个十分重要的方法。
额不会涉及具体的知识点#xff0c;只是总结点自己做题的时候遇到的比较巧妙的方法。
混沌排版请见谅
还有我也很菜有错…前言
闲的无聊懒得做题不如来水点博客。
虽然一直作为一个感性做题的选手但是理性层面上确实是分析题目初步做法的一个十分重要的方法。
额不会涉及具体的知识点只是总结点自己做题的时候遇到的比较巧妙的方法。
混沌排版请见谅
还有我也很菜有错误或者不完善的地方见谅/kk
Polya以后再更新 文章目录前言正题基本方法不重容斥寻找基准模型转换奇偶染色组合数→\rightarrow→矩阵乘法期望X计数幂次统计好题正题 基本方法
计数的基本方法来说的话大致能总结为几类
dp组合数学多项式其他
dpdpdp应该是比较早接触也是花样最多的一类方法一般需要考虑到状态的设立和优化方程的转移等部分。
组合数学的话主要通过找出题目的组合意义或者推式子得到。
而多项式一般都是需要使用生成函数也有可能是简单的卷积。
然而除了上面常见的计数存在一些其他灵活性的方法这类的题目一般都能够将整体的计数问题分散到一些小的统计上比如说SAM进行子串计数的过程。
当然也有可能是假计数比如实际上可能合法的方案数能够枚举完的。
不过这里不会赘述上面的几种方法因为这只是个总结经验的水博客不是教人计数的博客。 不重
重复问题应该是在正常的计数中最容易遇到的问题统计重复的方案对做法造成的影响很大比如来说
无标号计数这种一般来说这种是很难的问题因为一般的计数都需要有一个基准而这很经常是标号。统计的不是形成方案的方法而是方案很多的生成方法是会生成重复的方案的当然这个生成方法可能是你自己决定的或者题目给出的。
比较常见的应该就这两种情况了当我们的计数出现重复的时候就需要考虑换方法来去掉重复或者不计重复的部分。
容斥
啊又是一个很大的专题当然容斥是有两种作用的一种是来去掉重复一种是保证限制的合法。
比如经典的错排问题 我们可以枚举我们至少有多少个位置是不合法的设为kkk个那么不合法的位置就固定了答案就是 ∑k1n(nk)(−1)k(n−k)!\sum_{k1}^n\binom{n}{k}(-1)^k(n-k)!k1∑n(kn)(−1)k(n−k)! 不难发现容斥的一个好处是我们不需要去统计恰好而是去固定一些至少这样可以去掉一些麻烦的限制这是一个很常见的用处。
容斥还有一个好处是我们的容斥系数可以直接乘在方案中以节省很多的状态dpdpdp来说。
比如以题目[ARC101C] Ribbons on Tree来说 nnn个点之间两两配对要求配对点之间的路径覆盖整棵树求方案数对109710^971097取模 1≤n≤50001\leq n\leq 50001≤n≤5000 额看看我们的限制每条边都被覆盖至少一次那么我们容斥来说就是如果钦定kkk条边不能被覆盖容斥系数就是(−1)k(-1)^k(−1)k。 我们暴力切断不需要覆盖的边那么设fi,j,kf_{i,j,k}fi,j,k表示以iii为根的子树中目前联通块大小为jjj已经切断了kkk条边时的方案。 显然的切断一条边的时候容斥系数成了个−1-1−1那么我们完全没有必要用状态记录它而是直接维护目前的方案×容斥系数的和状态就缩成两维了。
至于很多的反演我认为这不需要在此篇中过多介绍。 寻找基准
基准是一个计数中不可或缺的东西。
拿最简单的过河卒问题来讲我们询问的兵的路线数量实际上是一个绝对的空间和时间也就是走的顺序的路径。
如果问题可以变为询问过河卒的路径能有多少种不同的形状旋转或者镜像得到的也算重复那么就是去掉了部分的基准。
而有的问题中基准并不会明显的给出所以可能正常的计数会导致大量的重漏此时我们需要寻找一个好的基准来计数。
拿无标号有根数的计数来讲我们不会算重的原理就是说我们将所有的子树按照一定的规律进行了排序此时就是确定了一个基准。
例题的话可以看P7888。 模型转换
一个很大的话题大部分的难的计数题都是会有一些十分复杂的条件的需要找到一个比较简单的条件来替换掉原来的条件。
当然的变换之后不可避免地会有按照新的条件来计的话算重的可能性此时就需要具体分析了。
奇偶染色
比如[AGC040C]Neither AB nor BA 一个包含A,B,CA,B,CA,B,C的序列每次可以选择相邻的两个除了ABABAB和BABABA的删去。 求有多少个长度为NNN的序列可以删完。 1≤N≤1071\leq N\leq 10^71≤N≤107 经典的奇偶染色把偶数位置的取反就变为了删除AA/BBAA/BBAA/BB然后就很好统计了。
组合数→\rightarrow→矩阵乘法
最经典的应该是https://www.luogu.com.cn/problem/P3746 求 (∑i0∞(nkikr))%p\left(\sum_{i0}^\infty \binom{nk}{ikr}\right)\% p(i0∑∞(ikrnk))%p 1≤n≤109,0≤rk≤501\leq n\leq 10^9,0\leq rk\leq 501≤n≤109,0≤rk≤50 其实就是在nknknk个物品中选出xxx个物品要求x%krx\%krx%kr直接矩阵乘法即可。
而大部分问题可以将组合意义和dp相互转换来转换成快速的矩阵乘法。
期望X计数 有限的期望题都是计数 −\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ - −不是我就对了 但是有时候运用期望的思想会让问题更加的简单。
当然一般这种时候正常的计数也是可行的只不过一般来说在每一步的总方案数不确定但是概率能确定的情况下我们不妨先算出期望再乘上总共的方案数就能得到答案。
原本有道例题的但是找不到了/cy
幂次
有时候我们会需要统计答案幂次的和假设是nkn^knk我们可以将转换为在nnn个数中选出有序可重的kkk个数此时我们就将一个幂次的问题转换为了一个较为复杂的计数。
如[NOI2009]管道取珠 给出一个大小为nnn和一个大小为mmm的栈每次选择一个栈弹出栈顶然后记录这个字母求所有弹出序列的弹出方案的二次方和。 1≤n,m≤5001\leq n,m\leq 5001≤n,m≤500 方案的平方可以视为两个人选出同一个序列的方案。 然后dpdpdp转移即可。 统计
有的时候计数题不仅需要统计方案数而是每个方案下某个值的和。
此时我们一般有以下解决方案
使用dpdpdp统计考虑方程是否会存在让某个状态的所有方案的加值的情况那么此时需要额外记录一个方案数的数组。组合意义考虑比如上面的幂次小结中便是用组合意义转化为了一般计数题。单独考虑单个东西产生的贡献。 好题
不知道写啥了记些好题罢
P6499-[COCI2016-2017#2]Burza51nod1667-概率好题51nod1597-有限背包计数问题[AGC013E]Placing SquaresCF1286D-LCC
