首页 > 其他分享 >反射容斥

反射容斥

时间:2023-09-30 20:11:28浏览次数:47  
标签:反射 碰到 直线 路径 容斥 条数 num

故事的起因是模拟赛遇到了一道题:
img

\(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

相关文章

  • 2.反射
    反射概述:反射允许对成员变量,成员方法和构造方法的信息进行编程访问;是从class字节码文件中获取的;获取Class对象Class.forName("全类名");类名.class;对象.getClass();利用反射获取构造方法:Class类中用于获取构造方法的方法:Constructor<?>[]getConstructors() ......
  • 容斥定理
    01容斥定理容斥定理(简单情况)对任意两个有限集合 A 和 B ,有=+-其中,分别表示 A ,B 的元素个数.推广结论:对于任意三个有限集合 A , B , C ,有= ++---+有限集合的计数方法1:利用容斥定理的上述两个公式计算有限集合的元素个数.有限集合的计数方法2:文氏图法,即首先根......
  • jsp 之反射型 xss 示例
    jsp代码如下:<%@pagecontentType="text/html;charset=UTF-8"pageEncoding="UTF-8"%><!DOCTYPEhtml><html><body><formaction=""method="get">姓名:<inputname="name"type......
  • golang 反射
    参考https://www.cnblogs.com/jiujuan/p/17142703.htmlfloat反射示例packagemainimport( "fmt" "reflect")funcmain(){ varxfloat64=1.2345 fmt.Println("==TypeOf==") t:=reflect.TypeOf(x) fmt.Println("type:&quo......
  • 反射 内置方法
    如何实现反射:classPeople:def__inti__(self,name,age):self.name=nameself.age=agedefsay(self):print('<%s;%s>'%(self.name,self.age))obj=People('猪猪同学',18)  classFtp:defput(self):print('正在执行上传功......
  • 反射
    反射是指对一个程序集中的元数据进行检查的过程。说明白一点,就是可以访问和使用一个dll里面所有的东西,并且是运行动态时的调用,而不是普通编译时的绑定,这样使程序更加的自由和灵活,但是性能较低。反射一般可以用于:插件的开发、特性和程序的动态调用等等。1.首先我们写一个类,实现他......
  • go 反射
     一.go反射介绍和定义 在Go语言中,反射机制是一种动态获取变量类型和值信息的机制,它可以让程序在运行时动态地获取对象的类型信息、调用对象的方法、修改对象的属性等。通过反射机制,Go程序可以更加灵活和可扩展,但同时也会带来一些性能开销和复杂度。在Go语言中,反射机制主......
  • 容斥原理应用Acwing890借鉴题解
    参考文献简单的容斥原理介绍请看下图:C++代码简单的容斥原理介绍请看下图:本题思路:将题目所给出的m个数可以看成是m位的二进制数,例如当p[N]={2,3}时,此时会有01,10,11三种情况而二进制的第零位表示的是p[0]上面的数字2,第1位表示p[1]上面的数字3所以当i=1时表示只选择2的......
  • 在 Net7.0环境下通过反射创建对象和调用方法
    一、介绍最近没事干,就用闲暇时间写点东西,也记录一下温习历程。老人说的好,好记性,不如烂笔头。时间一长,当时记忆的再清楚,都会变得模糊,索性就写博客记录下来,如果下次需要,直接打开博客就找到了,不用去网上乱找了。今天我要写一些有关反射创建类型实例和调用方法的文章,......
  • 反射修改String中的value属性(char[])
    上图结论:可以通过反射获取String对象的value属性,然后有两种方式修改:1.构建一个新的char[]数组进行替换 2.构建一个char[]指向同一对象,对该对象中的内容进行修改(即char[0='X'])反射结论:对于private修饰的字段,可以利用setAccessible(true)函数处理;同时,反射可以直接处理final或者s......