2013集训队论文答辩(高胜寒)演示文稿.ppt

浅谈环状计数问题,江苏省常州高级中学高胜寒,引言,在信息学竞赛中，经常会遇到计数问题，而其中很多有环状的模型。为解决此类问题，需要用到burnside引理plya定理和基础递推及其优化。,【例题】自创题：项链,长为n可旋转不可翻折的01项链，求包含长为k的给定字符串s的项链种类数（k=n）。20%的数据n=2060%的数据n=1000100%的数据k=30，n=109,算法一蛮力法,本题为环状计数问题，对于20%的数据可以枚举所有可能的满足包含给定串的情况。因为旋转被认为是相同的，所以对于每种情况将它旋转1到n格，使用位运算可以将暴力优化。时间复杂度O(2nn)空间复杂度O(2n),算法二脱离蛮力算法,不使用暴力枚举法，最关键的问题是必须解决旋转后相同这一问题。思考burnside引理或plya定理，如果把每个旋转都看成置换，则旋转后相同的项链可以认为同属一个等价类。如何求得等价类的数目呢？,burnside引理,burnside引理大致如下：设作用在集合X上的置换群G，对于所有gG，令Xg为X在置换g下元素不动的集合。则等价类数,不动类,所谓不动类，通俗地讲就是一种方案经旋转后变为自己。下面具体分析一下：设旋转了t格。,t,t,循环,由此可见，若要保持方案的不动，有：a1,a2,at=at+1,at+2,a2t即长为n的方案每t个数一个循环，由辗转相除原理可知实际上方案的循环节长为(n,i)，由此将数值代入burnside引理得：,fi的意义？,长为i的字符串，写若干遍变成长为n的包含给定字符串s的方案数。,递推,置换部分已经解决，剩下部分的可以用递推解决。考虑转移，可以记录长为t的串，当前匹配到第i位，如何转移到长t+1的串呢？,kmp字符串匹配,递推,求出kmp失配指针利用其进行转移得到方案数组f,问题在环上,n=5，s=010方案01101,考虑拼接,如之前的例子，得知转移时不仅需要记录当前串的匹配位置，还需要记录串首的情况。记录状态三维tab，表示长为t的串，此串有：最长同为s后缀和当前串前缀的a，及最长同为s前缀和当前串后缀的b。这样就可以考虑到a拼接在b后面形成s的情况。,拼接判断,如何判断ba是否可以拼接成功呢？方案一|a|+|b|=k方案二做k2预处理,可以发现反例，如n=10，s=101011方案1011001010有a=1011，b=1010,正解,遇到问题,在做递推时对于t，b两维并没有什么问题，而前缀a会遇到如下情况：n=10，s=100100，方案0010001001后缀b=1001，前缀a=00100而在实现时会将a=00这种情况也算在其中，虽然均符合条件，但同一个方案算了两次。,容斥原理,原因是之前红字“最长”这一定义没有用到，不过解决此问题也并不麻烦。对于一个s的后缀a，减去所有更长的以a为前缀的s的后缀的答案。如例子：s=100100将后缀00的答案减去后缀00100所得的答案就是环形数列恰以00为首的方案数。这样递推部分也被完美的解决了。,细节漏洞,结合burnside引理所推得公式，需要求得f(n,i)，有一种情况(n,i)k。,理论上短串是不能包含长串的。但考虑到f(n,i)的意义，这里需将短串重复写若干遍使其长为n再做判断的。如果(n,i)是k的循环节，则会存在满足要求的方案。,kmp循环节匹配问题,算法二分析,由burnside所推得公式，需要算出所有f1n，由三维状态递推完成，可采用滚动数组，转移复杂度为O(1)，所以总时间复杂度O(nk2)空间复杂度O(k2),算法三进一步优化,以上算法已经可以做到60%的数据了。然而递推与置换两方面都存在瓶颈，首先考虑递推部分。由于k比较小，枚举前缀a，b作为一维状态在长度t上转移。可以写出转移矩阵，将其自乘即可算出答案，使用快速幂将时间优化到log级。,再谈burnside,观察之前的公式：,可以发现其优化方向：由于(n,t)|n，所以(n,t)的数量级为sqrt(n)。,对于所有可能的f(n,t)，仅需求出其系数。枚举所有的q，(n,t)=q的充分必要条件为q|tq|n(n/q,t/q)=1,满足条件的t有phi(n/q)个,优化公式,根据刚才的推论可以得到最终的公式：,结合之前递推所得的结果，可以说本题基本完成了。,算法三分析,因子个数是sqrt(n)级别的，也就是要做这么多次快速幂矩阵乘法。所以可得：,空间复杂度O(k2lgn)时间复杂度O(),预计得分统计图,【加强版】,加强置换项链旋转、翻折后均算作相同从置换开始分析，推出带有翻折的公式。改变短串拼为长串的拼接方式。加强匹配项链不可包含多个给定的字符串改用AC自动机以处理多串问题。在处理短串包含长串时特殊处理。,小结,环状计数问题多种多样，但是万变不离其宗，使用以下方法便可顺利解决问题。,分析题目条件，写出置换,由置换推出所需公式,依据公式要求写递推转移,参考文献,陈瑜希,2008,plya计数法的应用SchaumsOutlineofDiscreteMathematics(离散数学)清华大学出版社,感谢,感谢CCF提供的一次展示的机会感谢前人对相关知识的不懈努力研究感谢曹文老师及钱雨杰提供的修改意见感谢大家耐心地听讲,欢迎提问,关于加强版问题,对于置换加强，题目加上了翻折操作。原先旋转操作的情况不变，需要对翻折操作讨论。所有翻折后再旋转都可以直接看成一次以不同位置为轴的翻折操作。如果把n元的环看成正n边形，那么它有n条对称轴，正好对应n个置换。,加强置换,这些对称轴要分奇偶情况讨论。当n为奇数时，所有对称轴均经过顶点。当n为偶数时，有一半对称轴经过顶点，另一半不经过顶点，只经过边的中点。,加强置换,由此可以发现n为奇数方案数为：当n为偶数时，方案数为：,加强置换,在两个公式中，均有gi，目的是和fi区别开来。它们之所以不同，主要是因为其拼接方式有所差异。对于旋转，是将首接在尾后面，而翻折时首尾可以分开考虑，均为对称翻折。所以此时总状态不变，只需要再做一次拼接预处理即可完成加强版题目。,加强匹配,对于多串匹配问