主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
【备份】ひかり(hikari)
最后更新于 2025-07-31 09:39:05
作者
奇犽
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
# ひかり(hikari) ## 题目背景 $$小杰...你就像光一样$$ $$但有时太过刺眼,使我无法直视你$$ $$即使这样,你还是肯跟我在一起吗?$$  ## 题目描述 在「光の境」中,定义地平线高度为 $0$,天际线高度为 $z$,一切建筑基于地平线或天际线。 有 $n$ 座灯塔,每座灯塔位于横坐标 $x_i$ 处,高度为 $h_i$,7月7日晚上亮起的概率为 $1/p_i$。灯塔可能建在地平线上或是天际线上,称作地灯塔与天灯塔。 (建在地平线上的灯塔塔顶位于纵坐标 $h_i$ 处,建在天际线上的灯塔塔顶位于纵坐标 $z-h_i$ 处) 7月7日是奇犽生日。那天晚上奇犽打了一个赌。奇犽随机选择一座灯塔,记作 $i$ 号灯塔,小杰从**剩余**的灯塔中随机选择一座灯塔,记作 $j$ 号灯塔,他们将登上塔顶。 如果灯塔 $i$ 与 $j$ 都被点亮,且奇犽能够看到小杰( $i$ 与 $j$ 号灯塔塔顶连线不穿过任何一座灯塔或任何一座灯塔塔顶 ),那么奇犽就会向小杰求婚。 ~~奇犽只是一时兴奋打了这个赌~~,他不知道他向小杰求婚的概率,所以来找你的帮忙,如果没有在一秒之内告诉他答案,他可能会杀了你哦~ (Tips:奇犽是个杀手) ## 输入格式 第一行输入两个整数 $n$,$z$,表示灯塔数量与天际线高度。 接下来 $n$ 行,每行输入三个整数 $x_i$ , $h_i$ , $p_i$ , $ex$ 为 $0$ 表示灯塔是天灯塔,$1$ 表示地灯塔。 ## 输出格式 一行输出一个整数 $ans$,表示奇犽求婚概率在模质数 $761521$ ~~(奇犽我爱你)~~ 意义下的乘法逆元 ## 样例 #1 ### 样例输入 #1 ``` 6 5 1 1 1 1 2 2 1 1 3 2 1 1 1 3 1 0 2 1 1 0 3 1 1 0 ``` ### 样例输出 #1 ``` 101537 ``` ## 样例 #2 ### 样例输入 #2 ``` 3 5 3 2 4 1 1 4 5 0 2 4 2 1 ``` ### 样例输出 #2 ``` 704477 ``` ## 提示 #### 样例1解释 $13/15$ 在模 $761521$ 意义下的乘法逆元是 $101537$  #### 数据范围 对于 $ 30\% $ 的数据,$n \le 300$。 对于 $ 40\% $ 的数据,$n \le 1000$。 对于另外 $ 10\% $ 的数据, $p_i = 1$。 对于另外 $ 20\% $ 的数据,所有 $ex = 1$ 或 所有 $ex = 0$。 对于另外 $ 10\% $ 的数据,不存在一个横坐标上既有天灯塔又有地灯塔。 对于 $ 100\% $ 的数据,$n \le 5000$ , $z,x_i,h_i,p_i\le10^9$。$0 \le ex \le1$ , $x_i,h_i,p_i$ 均为正整数。 保证同一横坐标处,地灯塔与天灯塔的高度之和小于 $z$ 。 #### 加强版 $n$ 座灯塔,每座灯塔上有 $a_i$ 个窗户,共 $m$ 个,每个窗户也作为灯塔塔顶考虑。 对于$ 100\% $的数据,$n \le 200$ , $m \le10^4$ , 即$O(nm\log_2m)$ #### 悄悄话 是这个[奇犽](https://baike.baidu.com/item/%E5%A5%87%E7%8A%BD%C2%B7%E6%8F%8D%E6%95%8C%E5%AE%A2) (他是小杰~~老婆~~) 不是这个[奇犽](https://www.luogu.com.cn/user/290606) (他是出题人) 改编自 DTOJ NOIP 2023 模拟 2 T2
正在渲染内容...
点赞
0
收藏
0