(⊙﹏⊙)不知道为什么比赛时候这个题和D题死推不出来,比赛完了5分钟ac,我大概脑子坏掉了.真的是超超超超级简单的一个题,但是我光顾着用数学公式推了所以推出来结果巨复杂(⊙﹏⊙)服了自己了.
有了g(lr)再来考虑w(lr),\[w(lr)=\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} g(ij) \]就跟g的表达式很像,但是这里不能直接再套用g关于p1的公式,因为g里面有很多的0是跟p2无关的,换句话说这些0并不是由p2[l-2]^p2[r]求出来的,所以要分类讨论.分析方法跟g是类似的,列一个表观察每个p2出现的规律,可以发现,这个规律是4个一循环的结构,设\[t=(r-l+1)\mod 4\]; 则当t==0时,所有的p2下标出现次数均为偶数次,也就是结果一定为0,t==2时,所有的p2下标出现次数均为奇数,这样的话即等于\[\sum_{i=l-1}^{r} p2[i] \],这个式子说明我们可以再用一个p2的前缀和p3来O(1)计算这个结果.这是比较简单的两种情况,另外两种是t==1和t==3,这两种一种是奇数项的出现次数为奇数偶数项为偶数,另一种是奇数项出现次数为偶数而偶数项出现次数为奇数,这意味着可以用一个分奇偶的前缀和来O(1)求得这个式子只不过仍需要分类讨论一次.若令p31[i]和p32[i]分别表示p2的奇偶前缀和,t=(r-l+1)%4 则w(lr)的表达式为
这个题一开始想歪了一直在想polya.带了半天队友节奏最后俩人都没整出来.
其实一开始就不该被给出的示意图带着走的,当时已经想到了剩下的是n-m段,但是关键在于没有想到怎么处理排列的去重.试了下用母函数分配出入度后来发现无法去除已经有圈的情况于是放弃.其实这时候该想想能不能换个方向用母函数,哎,总的来说还是太菜,做组合数学还是不行.
后来想了下,可以先完全去掉所有的标号,也就是说把所有的点当成同一种点,然后去解决把这n个点分为n-m条链的分法,最后把标号还原回去只需要乘以一个n!的全排列系数就好了.
这时候问题转化为n个相同的点,分为n-m个链条(单个节点自身也是一个链条)的分法,而且这种分法要考虑到空间对称(参考样例).我们可以设普通型母函数\[F(x)=a_0+a_1x+a_2x^2+...+a_nx^n\]来表示一条链的情况,幂次等于这条链条有多少个节点.由于不认为0个节点是一个链,所以\[a_0=0\] 然后当节点数多于1的时候由于空间对称要除以2,所以除了\[a_1\]之外所有的a都是1/2,也就是说对于一条链其母函数就是\[F(x)=x+1/2 x^2+1/2 x^3+1/2 x^4+....+1/2 x^n\]
得到了一条链的F(x),由母函数的性质可以得到k条链\[(k=m-n)\]的情况就是\[F(x)^k\]的结果中\[x^n\]的系数,只不过还要乘以一个\[n!\]的系数(因为我们之前把所有球都当作一样了所以要乘以一个全排列)再除以一个\[(n-m)!\](因为每次算出来的是所有可能的组合情况,但是这k条链条是不用排序的)
现在的话就是如何计算\[F(x)^k\]的结果中\[x^n\]的系数了,直接暴力肯定超时,考虑把\[F(x)\]的函数变换成更简单的形式.由级数的知识可以知道|x|<1时,\[ F(x)=(x-1/2 x^2)/1-x\]  那么\[F(x)^k=x^k(1-1/2 x)^k/(1-x)^k \]\[x^k\]好处理,这说明只需要求剩下的部分的\[x^(n-k)\]的系数就行了.看剩下的部分,这里的分母看上去很难操作,但是可以再用级数的方式变换一下 \[1/(1-x)=(1+x+x^2+x^3+x^4+...+x^n)\] 也就是说要求的部分变成了 \[(1-1/2 k)^k (1+x+x^2+x^3+x^4+...+x^n)^k\] 后面的这一坨\[1+x+x^2+x^3+x^4+...+x^n\]可以认为是一次一次乘到前面的.前面的\[(1-1/2 x)^k\]可以用二项式展开,每一项为\[C_k^{i} (-1/2 )^ix^i\] .这时候考虑计算"二项式展开中第i项对于最终结果的第j项的贡献度(i<=j)",可以想象一下i变成j是因为加了j-i个1次幂,而总共后面乘的是k个多项式,那么所有的情况也就是中学常学的"把j-i个物品分成k份允许有空集的分法"组合问题了,答案是\[C(j-i+k-1k-1)\],当时高中数学老师管这叫插隔板法还是什么来着emmmmm.这时候就容易计算了,在算贡献的时候再带上(-1/2)的i次幂就行了.
确实是不好想,尤其是在现场赛的环境下,感觉自己还是得更多的做难一点的题目.
去年校赛的时候感觉此题难的一批,,,昨天做polya练习题的时候做到了poj 2888去翻了下matrix67大神的十个利用矩阵乘法解决的经典题目中的第9题才恍然大悟.Oooooor2 做完这俩题再来看XDOJ的这个题已经是自然而然就可以搞出结果的了.
这个题的思想就是:把每一列3*1的小方格当成一个"珠子",把他可能的8种情况当成"颜色",然后这些颜色同时也代表状态,类似于poj2888的颜色相邻限制,这里的状态之间"能不能相邻"其实就是在状压dp里"能不能转移"的限制,不同状态之间的转移图如下(来自matrix67的那篇文章
主要是利用了斐波那契数列对mod1e9+9时二次剩余的性质.说起来这个性质也是很奇葩,只见过两次应用这个题目的情况,一个是这个题一个是/cf.
二次剩余的定义是 当存在某个x使得x^2 \equiv d(mod p)成立时,称"d是模p的二次剩余",当对任意不成立时,称" d是模 p的二次非剩余"
而对于斐波那契数列有更具体的性质:
想到了考虑每个点被多少个三角形包围,但是没想到怎么算.主要还是计算几何太萎le,完全没有想到可以极角排序处理emmm.
具体的就是,考虑每一个点被多少个三角形包含,但是直接考虑也不好计算,可以考虑反向计算出不被多少个三角形包含,这个计算就要用到极角排序了.循环遍历每个点,在每个xi点,都对所有的其他点(姑且称为角点吧)相对于这个xi点的极角做一个排序,然后利用三角形的性质,选一个方向(顺时针或者逆时针都行),依次考虑"以每个角点为最小极角与之角度差小于pi的最大角度点之间有多少个点",可能难以理解,画个图就好了,算出来点的数量p(p包含最大的那个点)之后C(p2)就是"包含当前最小角点的所有的不覆盖xi点的三角形数量",依次累加就好了.
另外,画个图就会发现,还需要考虑圆周转一圈的情况,所以要把排序后的极角数组复制一遍,而且复制出来的这个数组每个元素还要加2pi!(这个自己试试就知道了)
这个题目和3720很像,尤其是在应用对称性的时候.这种题目有个很有趣的地方就是他每次都是对局部进行刻画然后得到了全局的信息,或者可以这么说,按照某一种策略使得某种属性所有的状态都被考虑进去.在这里就是计算一个共线的点的问题,按照和题目3720算法本身的推其实是只能算出来"斜率为正"的一类斜线,但是算的是"所有的斜率为正"的斜线,也就是覆盖了每一种情况,那么剩下的情况其实只有水平竖直和斜率为负的斜线,但是由对称性可知斜率为负的斜线一定和斜率为正的斜线数量相等,因此只需要*2即可,而我自己一开始一直在纠结的问题就是怎么算出来这些反向斜线,其实最后全局考虑只需要把算出来的正向斜线情况*2即可.最后的结果就是C(3(m+1)*(n+1))-共线的三点数量.
wa的话有一个问题是,在gcd的算法中如果a和b有一个数字为0那么返回值就会是0,这种情况在这里的递推过程中是会出现问题的,需要注意让循环从2开始,也算是一个小小的坑吧.以前没有注意到.
很有意思的一个组合数学题.
整个题的最核心的思想就是,两个线段共线的判断!只要有两个点就可以确定一条线段(直线),那么只要再多一个点就可以确定这个点是否在和当前的这条线段共线了!所以两种算法的思想都在于一个2
第一种方法:最纠结的问题还是在于,怎么去重.想到了枚举角度的方法却没有想到怎么去重,还是思维不行.第一种方法是每次枚举所有可能的矩形,然后计算对角线的数量,这个很好算也就是有多少个矩形,直接(n-i+1)*(m-j+1)就行了.但是我们考虑的时候首先只考虑gcd(ij)==1的情况,这种情况一定说明这种对角线的角度第一次出现(因为我们从小到大枚举i和j),所以对答案贡献为正,还有一种情况是gcd(ij)==2,这说明之前已经出现过了这种对角线,所以这里要减去对应的数量,注意这里是最重要的:减去的是对应的数量,然后其他的gcd值不用+也不用-.原因就在于,如果你有一个4*4的或者3*3的矩形对角线重算了,那么在清除gcd为2的那一步当中其实就已经清除了所有的重复对角线!因为这个2会按照不同的起始点一直推下去. 继续阅读"[组合数学][数论][思维][空间对称转化][充要条件] UVALive 3720 Highways"
自己写了个有点繁杂的数位dp,本来一发过还有点高兴,但是看了前排dalao代码发现自己写的太复杂了.这个题其实只用组合数学就可以解emmmm
先上自己的屌丝做法:分段dp,从前往后,组合数学算下可以知道能预处理出来一段长度为n的可以包含前导0的数据的所有0的个数,我本来想的是用f(pmisf)表示当前是第p个数字,最大为m然后是否为上限isf表示状态,但是写着写着发现不用这么来.所以其实到最后程序里的isf就没有用(在发现这一点的时候我就该想到其实不用这么"dp"),把当前位为0特判一下加上后面的所有可能数字(这个也可以预处理),算完当前这一位之后往下一位继续算.最后由于我在f里面的枚举都是从0开始,所以等于说算出来的是"可以包含前导0的数的0的个数",所以在cal里面还要减去所有的前导0的个数.麻烦一批
再说dalao们的做法:其实这个前导0的问题很容易解决.从后往前算就ok了,每次算到一位的时候判断是不是0,不是0的话,可以想到当前位为0的话总共出现的次数是容易计算的:把整个数字从这个点分开成左右两段(不包括当前这一位),那么左边的数字*10^(右边的位数)如果当前为0那就不能这么算了(跟数位dp一个道理,isf的时候不能当成所有的情况来做)但是仍然很简单:只要左边不是最大的那个数字,右边仍然可以取到所以情况,所以这时候把左边-1乘上右边的10幂,再加上右边所有的本身的上限就行了.还是看代码比较好说.
其实我用了一种操蛋的贪心试了一下,所有的cf测试数据里只有一组会错.但是还没有搞明白为什么错了,也没有办法再继续证明正确性,所以还是放弃了去看tutorial,发现果然没思路就是dp.
然后这又不是一个正常的dp,甚至可以说不算是dp吧.要从一堆数字里选出来一个集合使得gcd为1.确实,涉及到集合就很难操作.但是可以发现,如果这个集合存在,他的size是很小的,这里可以作为一个突破点去想.如果考虑枚举集合的大小,是否能有简单的计算方法.现在需要求的东西可以转化为,是否存在至少一个集合使得他的size为i然后gcd为1,当然这个也不好直接算,但如果再加一维,再枚举gcd,看看会不会有进展:这时候要求的转化为,是否存在至少一个集合,size为i,gcd为j.可以设一个dp[i][j]表示这种集合的数量,然后尝试是否可以递推.这时候可以发现这i个数字一定是从j的倍数里选出来的,所有的选法有C(cntji)种,其中cntj是原数列中j的倍数的数量.而这些里面又有一些不符合要求的,是因为他们的gcd=k*j,然后可以发现这些不符合要求的数量就是dp[i][k*j],这就实现了从大问题往小问题推的转移了.然后就只剩下边界的问题了,这个边界也很有意思:因为只考虑k*j<=max(ai)的gcd,所以大于的就是0就可以了