当前位置: 首页 > news >正文

I - 太阳轰炸(组合数学Cnk n固定)

2023河南省赛组队训练赛(二) - Virtual Judge (vjudge.net)

背景:阿塔尼斯,达拉姆的大主教,在艾尔又一次沦陷之后指挥着星灵的最后一艘方舟舰:亚顿之矛。作为艾尔星灵数千年来的智慧结晶,亚顿之矛除了搭载了以太阳能碎片为核心的兵工厂之外,还配备了诸如汇聚射线、太阳能射线枪等威力强大的支援武器。而在这些武器中,最负盛名、也最让敌人胆寒的就是太阳轰炸。

太阳轰炸是一件威力巨大的对星球武器。在太阳轰炸开火时,亚顿之矛将聚集太阳能核心中的太阳能量,向目标坐标发射成百上千枚火焰飞弹。虽然这些火焰飞弹精准度较差,但太阳轰炸的高攻击频率仍然可以让地面上的敌人无法躲避,化为灰烬。

在这一次的行动中,阿塔尼斯的目标是一枚臭名昭著的虚空碎片。在俯视视角下,虚空碎片的投影是一个半径为 R1 的圆,太阳轰炸的攻击散布范围是一个半径为 R2 的圆。这两个圆的圆心均为原点 (0, 0)。太阳轰炸将射出 n 枚火焰飞弹,每一枚火焰飞弹等概率地落在攻击散布范围内每一个点上,所有火焰飞弹的落点相互独立。火焰飞弹的伤害范围是以落点为圆心,半径为 r 的圆。若火焰飞弹的伤害范围和虚空碎片的投影相交,则该枚火焰飞弹命中虚空碎片,造成 a 点伤害。若总伤害大于等于 h,则虚空碎片会被摧毁。

摧毁这枚虚空碎片对阿塔尼斯的战略部署非常重要,因此阿塔尼斯想要知道一次太阳轰炸能够摧毁这枚虚空碎片的概率。你需要输出答案对质数 109 + 7 取模的值。

Input

仅一行,包含六个整数 nR1, R2, rah (1 ≤ n ≤ 5 × 106, 1 ≤ R1, R2, r ≤ 108, 1 ≤ a, h ≤ 108),含义见题目描述。

Output

一个整数,表示答案。

Sample 1

InputcopyOutputcopy
3 2 4 1 1 1
636962896

Note

答案对质数 109 + 7 取模的定义:设 M = 109 + 7,可以证明答案可表示为一个既约分数 

,其中 p, q 均为整数且 q 模 M 不余 0。输出满足 0 ≤ x < M 且 x·q ≡ p ± od{M} 的整数 x

上图对应了样例中 R1 = 2, R2 = 4, r = 1 的情况。其中红色的圆是虚空碎片的投影,蓝色的圆是太阳轰炸的攻击范围。A, B, C 是三个可能的落点,其中 A, C 命中虚空碎片,而 B 没有命中虚空碎片。

题解:

1.概率为0,炮弹伤害全部命中也无法摧毁碎片

2.概率为1,炮弹的落范围R2 <= R1 + r

3.外面又一个环炮弹骗的范围

命中概率即为(R1 + r)*(R1 + r)/(R2 * R2) =  p1

未命中概率即为((R1*R2) - (R1 + r)*(R1 + r))/(R2 * R2) = p2

根据组合数学命中总概率为

Cnk*(p1)^k*p2^(n-k) + Cn(k+1)*(p1)^(k+1)*p2*(n-k-1) ....... 

Cnn*p1^n*p2^(n-n)

本题主要难点就是线性时间如何求出每一个Cnk

我们可以1*2*3..*n得到fa[n]

然后qpow(fa[n],mod-2)得到fa[n]的逆元g[n]

fa[n-1]的逆元就是g[n]*n依次类推

 

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
using namespace std;
#define int long long
const int N = 6e6 + 10; 
int mod = 1e9 + 7;
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
int fa[N];
int g[N];
int t[N];
int y[N];
int qpow(int x,int p)
{int a = 1;while(p){if(p&1)a = a*x%mod;x = x*x%mod;p /= 2;}return a;
}
int C(int n,int m)
{return fa[n]*g[m]%mod*g[n-m]%mod;
}
void solve()
{int n,r1,r2,r,a,h;cin >> n >> r1 >> r2 >> r >> a >> h;int k ;if(h%a == 0){k = h/a;}else{k = h/a + 1;}if(k > n){cout<<"0";return ;}if(r2 <= (r1 + r)){cout <<"1\n";return ;}fa[0] = g[0] = 1;int z = (r1 + r)*(r1 + r)%mod;int x = (r2*r2%mod - (r1 + r)*(r1 + r)%mod + mod)%mod;int c= r2*r2%mod; for(int i = 1;i <= n;i++){fa[i] = fa[i-1]*i%mod;}g[n] = qpow(fa[n],mod - 2);for(int i = n -1;i >= 0;i--){g[i] = g[i+1]*(i+1)%mod;}int zx = 1;for(int i = 1;i <= n;i++){zx = zx*c %mod;}t[0] = 1,y[0] = 1;for(int i = 1;i <= n;i++){t[i] = t[i - 1]*z%mod;y[i] = y[i-1]*x%mod; }int s = 0;for(int i = k;i <= n;i++){s = (s + (C(n,i) * t[i]%mod*y[n - i]%mod) %mod)%mod;}cout << s*qpow(zx,mod-2)%mod;}
signed main()
{
//	ios;int t = 1;
//	cin >> t;while(t--){solve();} 
}
//3 F
//5 B
//6 F
//9 F
//10 B
//12 F
//15 FB
//18 FB

相关文章:

I - 太阳轰炸(组合数学Cnk n固定)

2023河南省赛组队训练赛&#xff08;二&#xff09; - Virtual Judge (vjudge.net) 背景&#xff1a;阿塔尼斯&#xff0c;达拉姆的大主教&#xff0c;在艾尔又一次沦陷之后指挥着星灵的最后一艘方舟舰&#xff1a;亚顿之矛。作为艾尔星灵数千年来的智慧结晶&#xff0c;亚顿之…...

centos安装gitlab

更新系统 sudo yum -y update安装所需要的包 sudo yum -y install epel-release curl vim policycoreutils-python如果要安装并使用本地Postfix服务器发送通知&#xff0c;请安装Postfix&#xff0c;这里就不安装了&#xff1a; sudo yum -y install postfix安装后启动并启用…...

【洛谷 P1093】[NOIP2007 普及组] 奖学金 题解(结构体排序)

[NOIP2007 普及组] 奖学金 题目描述 某小学最近得到了一笔赞助&#xff0c;打算拿出其中一部分为学习成绩优秀的前 555 名学生发奖学金。期末&#xff0c;每个学生都有 333 门课的成绩:语文、数学、英语。先按总分从高到低排序&#xff0c;如果两个同学总分相同&#xff0c;再…...

【Hello Linux】进程优先级和环境变量

作者&#xff1a;小萌新 专栏&#xff1a;Linux 作者简介&#xff1a;大二学生 希望能和大家一起进步&#xff01; 本篇博客简介&#xff1a;简单介绍下进程的优先级 环境变量 进程优先级环境变量进程的优先级基本概念如何查看优先级PRI与NINI值的设置范围NI值如何修改修改方式…...

日期:Date,SimpleDateFormat常见API以及包装类

一.Date类 package com.gch.d1_date;import java.util.Date;/**目标:学会使用Date类处理时间,获取时间的信息*/ public class DateDemo1 {public static void main(String[] args) {// 1.创建一个Date类的对象:代表系统此刻日期时间对象Date d new Date();System.out.println(…...

嵌入式之ubuntu终端操作与shell常用命令详解

目录 文件和目录列表 基本列表功能 显示列表长度 过滤输出列表 浏览文件系统 Linux 文件系统 遍历目录 处理文件 创建文件 复制文件 制表键自动补全 重命名文件 删除文件 处理目录 创建目录 删除目录 ​编辑其他常用命令与操作 Uname命令 clear命令 返回上一级命令 显…...

【Shell学习笔记】6.Shell 流程控制

前言 本章介绍Shell的流程控制。 Shell 流程控制 和 Java、PHP 等语言不一样&#xff0c;sh 的流程控制不可为空&#xff0c;如(以下为 PHP 流程控制写法)&#xff1a; 实例 <?php if (isset($_GET["q"])) {search(q); } else {// 不做任何事情 }在 sh/bash…...

27k入职阿里测开岗那天,我哭了,这5个月付出的一切总算没有白费~

先说一下自己的个人情况&#xff0c;计算机专业&#xff0c;16年普通二本学校毕业&#xff0c;经历过一些失败的工作经历后&#xff0c;经推荐就进入了华为的测试岗&#xff0c;进去才知道是接了个外包项目&#xff0c;不太稳定的样子&#xff0c;可是刚毕业谁知道什么外包不外…...

服务端开发之Java备战秋招面试篇5

努力了那么多年,回头一望,几乎全是漫长的挫折和煎熬。对于大多数人的一生来说,顺风顺水只是偶尔,挫折、不堪、焦虑和迷茫才是主旋律。我们登上并非我们所选择的舞台,演出并非我们所选择的剧本。继续加油吧&#xff01; 目录 1.ArrayList与LinkedList区别&#xff0c; 应用场景…...

有趣的 Kotlin 0x11: joinToString,你真的了解嘛?

前言 之前使用 joinToString 函数也就是用逗号连接集合元素形成字符串&#xff0c;也没有细看它的参数&#xff0c;但是今天和 ChatGPT 聊天时&#xff0c;发现它给我输出了诸多内容。 joinToString joinToString()是Kotlin中一个非常有用的函数&#xff0c;它可以将集合的元…...

代码随想录算法训练营day46 | 动态规划之背包问题 139.单词拆分

day46139.单词拆分1.确定dp数组以及下标的含义2.确定递推公式3.dp数组如何初始化4.确定遍历顺序5.举例推导dp[i]139.单词拆分 题目链接 解题思路&#xff1a;单词就是物品&#xff0c;字符串s就是背包&#xff0c;单词能否组成字符串s&#xff0c;就是问物品能不能把背包装满。…...

DPDK中的无锁共享数据结构

目录背景解决方法共享内存无锁操作新/老共享数据结构rte_ringrefcnt延迟释放方法1&#xff1a;读的线程来释放方法2&#xff1a;释放线程等到读线程轮询一轮参考背景 dpvs多线程&#xff0c;如何做到节约内存、高性能之间的均衡。 解决方法 共享内存 多线程共享内存&#x…...

【使用两个栈实现队列】

文章目录一、栈和队列的基本特点二、基本接口函数的实现1.栈的接口2.创建队列骨架3.入队操作4.取出队列元素5.返回队首元素6.判断队列是否为空7.销毁队列总结一、栈和队列的基本特点 栈的特点是后进先出&#xff0c;而队列的特点是先进先出。 使用两个栈实现队列&#xff0c;必…...

web,h5海康视频接入监控视频流记录一

项目需求&#xff0c;web端实现海康监控视频对接接入&#xff0c;需实现实时预览&#xff0c;云台功能&#xff0c;回放功能。 web端要播放视频&#xff0c;有三种方式&#xff0c;一种是装浏览器装插件&#xff0c;一种是装客户端exe&#xff0c;还有就是无插件了。浏览器装插…...

做毕业设计,前端部分你需要掌握的6个核心技能

其实前端新手如果想要自己实现一套毕业设计项目并非简单的事&#xff0c;因为之前很多人一直还停留在知识点的阶段&#xff0c;而且管理系统和C端网站都需要开发&#xff0c;但现在需要点连成线了。所以在启动项目开发之前呢&#xff0c;针对前端部分&#xff0c;我列举一些非常…...

Read book Netty in action(Chapter VIII)--EventLoop and thread model

前言 简单地说&#xff0c;线程模型指定了操作系统、编程语言、框架或者应用程序的上下文中的线程管理的关键方面。显而易见地&#xff0c;如何以及何时创建线程将对应用程序代码的执行产生显著的影响&#xff0c;因此开发人员需要理解与不同模型相关的权衡。无论是他们自己选…...

番外11:使用ADS对射频功率放大器进行非线性测试3(使用带宽5MHz的WCDMA信号进行ACLR测试)

番外11&#xff1a;使用ADS对射频功率放大器进行非线性测试3&#xff08;使用带宽5MHz的WCDMA信号进行ACLR测试&#xff09; 其他测试&#xff1a; 番外9&#xff1a;使用ADS对射频功率放大器进行非线性测试1&#xff08;以IMD3测试为例&#xff09; 番外10&#xff1a;使用AD…...

Linux libpqxx 库安装及使用

记录一下linux安装 libpqxx遇到的一些问题 1.准备安装包&#xff1a; 1.准备安装包&#xff0c;以libpqxx-4.0.1.tar.gz为例子 链接如下&#xff1a;https://launchpad.net/libpqxx/milestone/4.0.1 2.上传并安装 上传到安装目录并安装&#xff0c;我是放到/use/local下面 c…...

如何使用COM-Hunter检测持久化COM劫持漏洞

关于COM-Hunter COM- Hunter是一款针对持久化COM劫持漏洞的安全检测工具&#xff0c;该工具基于C#语言开发&#xff0c;可以帮助广大研究人员通过持久化COM劫持技术来检测目标应用程序的安全性。 关于COM劫持 微软在Windows 3.11中引入了(Component Object Model, COM)&…...

Cartesi 举办的2023 黑客马拉松

Cartesi 是具有 Linux 运行时的特定于应用程序的Rollups执行层。Cartesi 的特定应用程序 Optimistic Rollup 框架使区块链堆栈足够强大&#xff0c;开发人员可以构建计算密集型和以前不可能的去中心化实例。Cartesi 的 RISC-V 虚拟机支持 Linux 运行时环境&#xff0c;允许像你…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...