故事的起因是模拟赛遇到了一道题:
\(N,M\le 1e7\)
赛时想到了其实可以去枚举原地不动的步数,然后catalan去计算方案数,但是有一个问题,就是这个限制:这个过程不能走出格子
这就相当于说我有一个栈,大小为m,要放入i个数,2*i次操作每次选择放入和拿出的方案数,但是栈不能取空,同时也不能爆栈
赛后才知道,这是经典容斥,叫做反射容斥
我们知道catalan的求法,把第一次越过y=x,即碰到y=x+1的这条直线的路径后面部分翻折,所以这样的路径的终点都会结束在一点上,所以所有不合法直线的条数,是可以看作是从起点到某点(对称过去的)路径的方案数
但是现在我们相当于有两条线,有一个朴素的容斥思想:
全部的路径条数-碰到第一条线的路径条数-碰到第一条线的路径条数+同时碰到第一第二条线的路径个数
可是如何算最后一项是个难题,因为这条路径可能先碰一下第一条线,再碰一下第二条线如此往复。。。
我们将每条路径按照某种标准分类,体现为依次碰到两条线的顺序及次数,每碰到第一条线记一个A,第二条线记一个B,如ABABAB
多次重复碰一条线只记第一次,如AAAAA=A
因为我们知道,从第一次碰到的地方翻折,已经所有非法直线汇聚一点,不需要更多的分类标准了
那么我们就可以像普通容斥一样
\(\varnothing-(A)_{num}-(B)_{num}+(AB)_{num}+(BA)_{num}....\)
如何去算 $ string_{num} $ 就成了首要问题
我们可以算出一个string后终点落点,每次对称都将目前终点按直线对称,然后就直接算两点间路径条数即可
如果落点落到了n步都走不到的地方,就不用继续递归下去了,因为落点对称只会越来越远
所以两条直线相距越远,递归越快,大概是 \(O(n/len)\) len为直线间距离
标签:反射,碰到,直线,路径,容斥,条数,num From: https://www.cnblogs.com/Linnyx/p/17738161.html