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

2021牛客OI赛前集训营-提高组(第三场)T2交替

2021牛客OI赛前集训营-提高组(第三场)

题目大意

一个长度为nnn的数组aaa,每秒都会变成一个长度为n−1n-1n1的新数组a′a'a,其变化规则如下

  • 如果当前数组aaa的大小nnn为偶数,则对于新数组a′a'a的每一个位置i(1≤i<n)i(1\leq i<n)i(1i<n)ai′=ai+ai+1a'_i=a_i+a_{i+1}ai=ai+ai+1
  • 如果当前数组aaa的大小nnn为奇数,则对于新数组a′a'a的每一个位置i(1≤i<n)i(1\leq i<n)i(1i<n)ai′=ai−ai+1a'_i=a_i-a_{i+1}ai=aiai+1

最终数组经过n−1n-1n1秒后变为一个数字,求这个数字对109+710^9+7109+7取模后的结果。


题解

通过打表可以发现,当nnn为偶数时,aia_iai对答案的贡献为(−1)t×Cn/2−1t(-1)^t\times C_{n/2-1}^{t}(1)t×Cn/21t,其中t=⌊i−12⌋t=\lfloor\dfrac{i-1}{2}\rfloort=2i1

如果nnn为偶数,则直接用上面的规律来求即可。如果nnn为奇数,那么操作一次,将nnn变为偶数,再用上面的规律来求即可。

当然,考场上可以直接用打表发现的规律,但学习要严谨,所以下面给出证明。

用多项式a1x+a2x2+⋯+anxna_1x+a_2x^2+\cdots+a_nx^na1x+a2x2++anxn表示当前的状态,用xix^ixi的系数表示当前第iii个位置的值。

  • 对于长度为偶数变为奇数的操作,相当于原来的多项式乘上(1+1x)(1+\dfrac 1x)(1+x1)
  • 对于长度为奇数变为偶数的操作,相当于原来的多项式乘上(1−1x)(1-\dfrac 1x)(1x1)

那么nnn每减去2,则多项式乘上(1−1x2)(1-\dfrac{1}{x^2})(1x21)

对于偶数的nnn,多项式要乘上(1−1x2)n/2−1(1+1x)=(1−Cn/2−111x2+Cn/2−121x4−⋯)(1+1x)(1-\dfrac{1}{x^2})^{n/2-1}(1+\dfrac 1x)=(1-C_{n/2-1}^1\dfrac{1}{x^2}+C_{n/2-1}^2\dfrac{1}{x^4}-\cdots)(1+\dfrac 1x)(1x21)n/21(1+x1)=(1Cn/211x21+Cn/212x41)(1+x1)。最后的答案就是xxx的系数。

我们考虑如何求xxx的系数。对于最初多项式中的xix^ixi

  • 如果iii是奇数,则xix_ixi可以和(−1)tCn/2−1t1xi−1(-1)^tC_{n/2-1}^{t}\dfrac{1}{x^{i-1}}(1)tCn/21txi11相乘来得到xxx的项
  • 如果iii是偶数,则xix_ixi可以和(−1)tCn/2−1t1xi−2×1x(-1)^tC_{n/2-1}^{t}\dfrac{1}{x^{i-2}}\times \dfrac 1x(1)tCn/21txi21×x1相乘来得到xxx的项

其中t=⌊i−12⌋t=\lfloor\dfrac{i-1}{2}\rfloort=2i1

那么就可以得到开头的结论。

时间复杂度为O(n)O(n)O(n)

code

#include<bits/stdc++.h>
using namespace std;
int n;
long long ans=0,a[100005],jc[100005],ny[100005];
long long mod=1000000007;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
long long C(int x,int y){return jc[x]*ny[y]%mod*ny[x-y]%mod;
}
int main()
{scanf("%d",&n);jc[0]=1;for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;ny[n]=mi(jc[n],mod-2);for(int i=n-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%mod;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}if(n==1){printf("%d",(a[1]%mod+mod)%mod);return 0;}if(n%2==1){--n;for(int i=1;i<=n;i++){a[i]=(a[i]-a[i+1]+mod)%mod;}}for(int i=1;i<=n;i++){int x=(n-1)/2,y=(i-1)/2;if(y&1) ans=(ans-C(x,y)*a[i]%mod+mod)%mod;else ans=(ans+C(x,y)*a[i]%mod+mod)%mod;}printf("%lld",ans);return 0;
}

相关文章:

2021牛客OI赛前集训营-提高组(第三场)T2交替

2021牛客OI赛前集训营-提高组&#xff08;第三场&#xff09; 题目大意 一个长度为nnn的数组aaa&#xff0c;每秒都会变成一个长度为n−1n-1n−1的新数组a′aa′&#xff0c;其变化规则如下 如果当前数组aaa的大小nnn为偶数&#xff0c;则对于新数组a′aa′的每一个位置i(1≤…...

论文投稿指南——中文核心期刊推荐(金融)

【前言】 &#x1f680; 想发论文怎么办&#xff1f;手把手教你论文如何投稿&#xff01;那么&#xff0c;首先要搞懂投稿目标——论文期刊 &#x1f384; 在期刊论文的分布中&#xff0c;存在一种普遍现象&#xff1a;即对于某一特定的学科或专业来说&#xff0c;少数期刊所含…...

华为OD机试 - 不等式(C 语言解题)【独家】

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧文章目录 使用说明本期题目:不等式题…...

90后老板用低代码整顿旅行社,创2000万年收,他是怎么做到的?(真实)

热爱旅游的92年成都小伙猴哥&#xff0c;大学毕业后开了一家旅行社&#xff0c;主要从事川藏、云南定制游服务。 从今年春节开始&#xff0c;国内各地旅游业开始复苏&#xff0c;向旅行社打电话咨询的人越来越多。 旅游的人多是好事&#xff0c;也是一种烦恼&#xff0c;因为…...

Apache Dubbo 存在反序列化漏洞(CVE-2023-23638)

漏洞描述 Apache Dubbo 是一款轻量级 Java RPC 框架 该项目受影响版本存在反序列化漏洞&#xff0c;由于Dubbo在序列化时检查不够全面&#xff0c;当攻击者可访问到dubbo服务时&#xff0c;可通过构造恶意请求绕过检查触发反序列化&#xff0c;执行恶意代码 漏洞名称Apache …...

【YOLO】YOLOv8训练自定义数据集(4种方式)

YOLOv8 出来一段时间了&#xff0c;继承了分类、检测、分割&#xff0c;本文主要实现自定义的数据集&#xff0c;使用 YOLOV8 进行检测模型的训练和使用 YOLOv8 此次将所有的配置参数全部解耦到配置文件 default.yaml&#xff0c;不再类似于 YOLOv5&#xff0c;一部分在配置文件…...

linux重置root用户密码

重置root密码 法一&#xff1a;rd.break 第 1 步&#xff1a;重启系统编辑内核参数 第 2 步&#xff1a;找到 linux 这行&#xff0c;在此行末尾空格后输入rd.break &#xff08;End键也可直接进入行尾&#xff09; 成功后显示页面为&#xff1a; 第 3 步&#xff1a;查看。…...

【DBC专题】-10-CAN DBC转换C语言代码Demo_接收Rx报文篇

案例背景(共15页精讲)&#xff1a; 该篇博文将告诉您&#xff0c;CAN DBC转换C语言代码Demo&#xff0c;只需传递对应CAN信号关联参数&#xff0c;无需每个信号"左移"和"右移"&#xff0c;并举例介绍&#xff1a;在CANoe/Canalyzer中CAPL中的应用&#xff…...

AtCoder292 E 思维

题意&#xff1a; 给定一副n(n≤3000)n(n\leq 3000)n(n≤3000)个顶点&#xff0c;mmm条有向边的图&#xff0c;可以在图中添加有向边&#xff0c;求添加的最少边数&#xff0c;使得这副图满足&#xff1a;如果顶点aaa到顶点bbb有边&#xff0c;顶点bbb到ccc右有边&#xff0c;…...

20230309英语学习

What Is Sleep Talking? We Look at the Science 为什么人睡觉会说梦话&#xff1f;来看看科学咋说 Nearly everyone has a story about people talking in their sleep.Though it tends to be more common in children, it can happen at any age:A 2010 study in the jour…...

CAD转换PDF格式怎么弄?教你几种方法轻松搞定!

CAD是从事与艺术创作相关等行业的打工人们必需的工作软件&#xff0c;可以用来完成建筑设计图、设计图纸等。在日常的工作中&#xff0c;一些伙伴经常需要传输图纸给合作方来完成探讨。但是CAD图纸需要使用专业软件才能打开&#xff0c;这就给文件传送带来了一定的困难。而且传…...

AtCoder 259E LCM

题意&#xff1a; 以唯一分解形式给出nnn个数&#xff1a; aipi,1ei,1pi,2ei,2...pi,tei,ta_{i}p_{i,1}^{e_{i,1}}p_{i,2}^{e_{i,2}}...p_{i,t}^{e_{i,t}} ai​pi,1ei,1​​pi,2ei,2​​...pi,tei,t​​ 现在可以将某个数改为111&#xff0c;求所有改法中&#xff0c;有多少个…...

MQTT协议-取消订阅和取消订阅确认

MQTT协议-取消订阅和取消订阅确认 客户端向服务器取消订阅 取消订阅的前提是客户端已经通过CONNECT报文连接上服务器&#xff0c;并且订阅了一个主题 UNSUBSCRIBE—取消订阅 取消订阅的报文同样是由固定报头可变报头有效载荷组成 固定报头由两个字节组成&#xff0c;第一个…...

90后小伙,用低代码“整顿”旅游业,年入2000万,他是怎么做到的?

热爱旅游的92年成都小伙猴哥&#xff0c;大学毕业后开了一家旅行社&#xff0c;主要从事川藏、云南定制游服务。 从今年春节开始&#xff0c;国内各地旅游业开始复苏&#xff0c;向旅行社打电话咨询的人越来越多。 旅游的人多是好事&#xff0c;也是一种烦恼&#xff0c;因为…...

C51---PWM 脉冲宽度调制

1.PWM:脉冲宽度调制,它是通过一系列脉冲宽度进行调制&#xff0c;等效出所需要的波形&#xff08;包含形状以及幅值&#xff09;。对模拟信号电平进行数字编码。也就是说通过调节占空比的变化来调节信号、能量等的变化&#xff0c;占空比就是指在一个周期内&#xff0c;信号处于…...

毕业设计 基于51单片机WIFI智能家居系统设计

基于51单片机WIFI智能家居系统设计1、毕业设计选题原则说明&#xff08;重点&#xff09;2、项目资料2.1 系统框架2.2 系统功能3、部分电路设计3.1 STC89C52单片机最小系统电路设计3.2 ESP8266 WIFI电路设计3.3 DHT11温湿度传感器电路设计4、部分代码展示4.1 LCD12864显示字符串…...

Nginx服务优化措施与配置防盗链

目录 一.优化Nginx的相关措施 二.隐藏/查看版本号 三.修改用户与组 四.设置缓存时间 五.日志切割脚本 六.设置连接超时控制连接访问时间 七.开启多进程 八.配置网页压缩 九.配置防盗链 1.配置web源主机&#xff08;192.168.79.210 www.zhuo.com&#xff09; 1.1 安装…...

Java 某厂面试题真题合集

哈喽~大家好&#xff0c;这篇来看看Java 某厂面试题真题合集。 &#x1f947;个人主页&#xff1a;个人主页​​​​​ &#x1f948; 系列专栏&#xff1a;【日常学习上的分享】 &#x1f949;与这篇相关的文章&#xff1a; Spr…...

很特别的5G市场,5.75亿部手机,却有11亿5G用户,这是怎么了?

中国在5G商用方面已取得了巨大的成绩&#xff0c;这是毋庸置疑的&#xff0c;不过近期公布的一份数据却相当特别&#xff0c;5G手机用户数为5.75亿&#xff0c;而开通了5G套餐的用户数却已超过11亿&#xff0c;这数据对比有点意思。中国在5G商用方面推进很快&#xff0c;建成的…...

go modules

文章目录1. 简介示例1. 示例——同一项目2. 示例——不同项目3. 示例——添加远程模块依赖库1. 简介 go module是Go1.11版本之后官方推出的版本管理工具&#xff0c;并且从Go1.13版本开始&#xff0c;go module将是Go语言默认的依赖管理工具。到今天Go1.14版本推出之后Go modu…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

[USACO23FEB] Bakery S

题目描述 Bessie 开了一家面包店! 在她的面包店里&#xff0c;Bessie 有一个烤箱&#xff0c;可以在 t C t_C tC​ 的时间内生产一块饼干或在 t M t_M tM​ 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC​,tM​≤109)。由于空间…...