首页 > 其他分享 >[Trick] 格路记数 - 反射容斥

[Trick] 格路记数 - 反射容斥

时间:2024-10-05 19:34:00浏览次数:5  
标签:直线 bc 线段 对称点 容斥 Trick 对称 格路

Perface

模拟赛不会被冲烂了。

Problem I

从 \((0,0)\) 到 \((n,m)\) 方案数。

解法:
\(C(n+m,m)\)。

Problem II

从 \((0,0)\) 到 \((n,m)\) 方案,但是不能经过 \(y=x+b\) 的直线。

解法:
考虑映射法。

以一条路径第一次碰到直线的位置为起点,之后所有的路线和 \(y=x+b\) 对称,这样可以不重不漏的映射完每一条路线。我们发现,这些路径的终点都是 \((m-b,n+b)\)。

答案为:\(C(n+m,n)-C(m+n,m-b)\)

Problem III

从 \((0,0)\) 到 \((n,m)\) 方案,但是不能经过 \(y=x+b\) 和 \(y=x+c\) 的直线。

image

当第一次碰到蓝色线段时,我们进行翻折。

image

碰到红色线段,也就是对称的黑色线段时,再次翻折。

image

因此,穿过两次线段的我们也映射完了。

观察一下,本质上就是将终点与线段进行对称。

对于一条线依次经过了 \(y=x+b\),\(y=x+c\),记反射序列为 \(bc\),但是如果经过一条线两次 \(bbc\) 我们也看做 \(bc\),因为我们记第一次碰到折线为对称点做到不重不漏。

那么,答案就是 \(ans=\empty-b-c+bc+cb-bcb-cbc+bcbc+cbcb-...\) (容斥原理)

因此,我们需要推出一个对称点的公式,快速求出 \(cbcbcb\) 点的对称坐标。

不难发现,本质上就是线和终点关于线对称,不清楚的直接看图:

image

容易知道一个点 \((x,y)\) 对于 \(y=x+b\) 对称点为 \((y-b,x+b)\),直线为 \(y=x+c\) 变为 \(y=x+2b-c\),我们只需要动态维护两条直线然后模拟即可。

考虑边界情况。不难发现每两次坐标会变化 \(2|b-c|\),也就是时间复杂度为 \(O(\frac{n+m}{|b-c|})\)。

被创飞了。

标签:直线,bc,线段,对称点,容斥,Trick,对称,格路
From: https://www.cnblogs.com/g1ove/p/18448337

相关文章

  • 反射容斥
    反射容斥恋のうたあとどれくらいの距離を月へ歩いたらあとどれくらいの寒い夜を重ねたらあとどれくらいのさよならを流したらまぶたの奥の泉が枯れ果てるとか千年後もきっと続くだろうそう思ってた空洞を満たしてあふれてしまうほどのこの気持ちはなんだ?新しい風を......
  • [算法] 容斥
    对于某些毒瘤计数题,经常会出现统计重复或遗漏的问题,这时候就可能需要容斥一下容斥原理先从一个经典的例子入手:有三个学科,设为$S_1,S_2,S_3$,有一堆人选不同的学科,现已知选每门学科各自有多少人选,求一共有多少人选学科;根据题意,我们要求的就是:$\midS_1\bigcupS_2\bigc......
  • Tricks(长期更新)
    会很杂,尽量分类,每个trick会配题。难以分类的难以分类可能只是自己太菜了。曼哈顿距离与切比雪夫距离的转化对于两点\((x_1,y_1),(x_2,y_2)\),曼哈顿距离为\(|x_1-x_2|+|y_1+y_2|\),切比雪夫距离为\(\max(|x_1-x_2|,|y_1-y_2|)\)。画图可以发现到原点的曼哈顿距离为\(1\)的点形......
  • 位运算 之 小 trick
    异或 只出现一次的数字(其他两次) 136.只出现一次的数字一串数中,每个数都出现2次,只有一个数出现1次,求出这个数。考察异或的性质,根据a^a=0,a^0=a那么就对每个数异或一下即可。然后根据交换律,每个数都异或了之后,相同的都归0了,剩下一个就自动求出来了。大概是这样(找不到C+......
  • 关于离散化+Trick
    离散化干嘛用的不多说。你不会去问度娘吗板板经常忘又懒得找。遂写一模板暂存。//a为原数组,b为a的副本voidversion1(){ sort(b+1,b+1+n); intsiz=unique(b+1,b+1+n)-b-1; for(inti=1,k;i<=n;i++) a[i]=lower_bound(b+1,b+1+siz,a[i])-b-1;}unordered_map<int,i......
  • 一些常用tricks,基础知识收录
    uoj转,YAML的ppt格式不想改了,将就看看吧|一些常用tricks,基础知识收录byzsjchildren:|题目链接:T1:CF504EMishaandLCPonTreeT2:LuoguP2617DynamicRankingsT3:LuoguP4197PeaksT4:LuoguP4690[Ynoi2016]镜中的昆虫T5:H1079.E.‘MinamiKotori......
  • [trick] 减半警报器
    适用题目\(\rightarrow\)高速判断是否合法,但是不知道什么时候应该判断核心思想\(\rightarrow\)鸽巢原理每个警报所监视的所有集合\(S\)的\(sum\)要达到\(d\),说明集合内至少有个元素的值大于等于\(\frac{d}{|S|}\),那我们把\(\frac{d}{|S|}\)作为警报数值,放在......
  • 【MATLAB源码-第227期】基于matlab的北方苍鹰优化算法(NGO)机器人栅格路径规划,输出做
    操作环境:MATLAB2022a1、算法描述鼠群优化算法(RatSwarmOptimization,RSO)简介鼠群优化算法(RatSwarmOptimization,RSO)是一种模仿鼠类群体觅食行为的优化算法。该算法属于群体智能算法,通过模拟鼠群在复杂环境中寻找食物的行为,来解决各种优化问题。鼠类在觅食过程中表现......
  • YoloV8 trick讲解
    1.将YOLOv5的 C3结构换成了梯度流更丰富的 C2f结构:C3C3模块的设计灵感来自CSPNet,其核心思想是将特征图的部分通道进行分割和并行处理,目的是减少冗余梯度信息,同时保持较高的网络表达能力。C3结构与传统的残差结构类似,但有一些关键改进。C3结构的具体组成如下:输......
  • 『做题记录』厉害trick集
      不出意外的话,这就是我最后的波纹了吧。  当然以后还会继续的。减半警报器  这个trick能将\(n^2\)的东西硬生生优化到\(n\log^2\),还是很厉害的trickP7603[THUPC2021]鬼街Description  鬼街上经常有灵异事件,每个灵异事件会导致编号为\(x\)的质因子的房子......