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

2023NOIP A层联测6 数点

题目大意

给你一个排列 p p p,对于每一个 i i i,我们在平面上,放置一个点 ( i , p i ) (i,p_i) (i,pi)。对于坐标上下限都在 1 ∼ n 1\sim n 1n内的全体 ( n ( n + 1 ) 2 ) 2 (\frac{n(n+1)}{2})^2 (2n(n+1))2矩形,求每个矩形内部点数的 k k k次方之和。

形式化地,请你计算

∑ 1 ≤ l ≤ r ≤ n ∑ 1 ≤ d ≤ u ≤ n ∣ { i ∣ l ≤ i ≤ r ∨ d ≤ p i ≤ u } ∣ \sum\limits_{1\leq l\leq r\leq n}\sum\limits_{1\leq d\leq u\leq n}|\{i|l\leq i\leq r\vee d\leq p_i\leq u\}| 1lrn1dun{ilirdpiu}

1 ≤ n ≤ 1 0 5 , 1 ≤ k ≤ 3 1\leq n\leq 10^5,1\leq k\leq 3 1n105,1k3


题解

我们可以考虑拆贡献,点数的 k k k次方可以看成选 k k k个点的方案的线性组合。

什么意思呢?就是在这 n n n个点中有序地可重地选择 k k k个点,将所有包含这 k k k个点的矩形的贡献 + 1 +1 +1,注意所有从 n n n个点中有序地可重地选 k k k个点的方案都要被计算贡献。

为什么可以这样呢?对于每个矩形,设这个矩形内的点数为 t t t,在这个矩形中有序地可重地选 k k k个点的方案数为 t k t^k tk,也就是说这个矩形在上面计算贡献的时候将贡献加了 t k t^k tk次一。

下面,我们来求 k k k为不同的值时的答案。

k = 1 k=1 k=1

对每个点 ( x , p x ) (x,p_x) (x,px),答案的贡献增加 x × ( n − x + 1 ) × p x × ( n − p x + 1 ) x\times (n-x+1)\times p_x\times (n-p_x+1) x×(nx+1)×px×(npx+1)

k = 2 k=2 k=2

我们考虑选的两个点相同的情况和两个点不同的情况。

对于两个点相同的情况,这其实就是 k = 1 k=1 k=1的情况,每种情况会被算一次。

对于两个点不同的情况,我们可以分为顺序对和逆序对来考虑:

  • 对于顺序对 x < y , p x < p y x<y,p_x<p_y x<y,px<py,其贡献为 x × p x × ( n − y + 1 ) × ( n − p y + 1 ) x\times p_x\times (n-y+1)\times (n-p_y+1) x×px×(ny+1)×(npy+1),将 x × p x x\times p_x x×px存入树状数组中,再用 ( n − y + 1 ) × ( n − p y + 1 ) (n-y+1)\times (n-p_y+1) (ny+1)×(npy+1)来乘即可
  • 对于逆序对 x < y , p x > p y x<y,p_x>p_y x<y,px>py将排列翻转之后按顺序对的方法来做即可

因为选点是有序的,每种顺序对和逆序对都用两种选法被选到,所以两个点不同的情况的贡献要乘 2 2 2

k = 3 k=3 k=3

k = 1 k=1 k=1的贡献计算一次(三次选择同一个点), k = 2 k=2 k=2的贡献计算两次(三次选择两个不同的点),下面再考虑三次选择三个不同的点的贡献。

分为两种本质不同的情况:

情况1
------
|*   |
| *  |
|  * |
------

这种情况出现了 2 2 2次(按 i i i左右翻转,总共有 2 2 2次),用两个树状数组维护即可。

情况2
------
|  * |
|*   |
| *  |
------

这种情况总共出现了 4 4 4次(按 i i i左右翻转,按 p i p_i pi上下翻转,四个角度各一次,总共有 4 4 4次),用线段树来维护即可。可以在加入第一个点时直接在对应位置上加数,在加入第二个点时将其后缀乘上对应的数,再加入第三个点时查询前缀和。

因为选点是有序的,每种顺序对和逆序对都用六种选法被选到,所以两个点不同的情况的贡献要乘 6 6 6

时间复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)

code

#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
const long long mod=998244353;
int n,K,p[100005];
long long tr1[100005],tr2[100005];
long long s[500005],hv[500005],ly[500005];
int lb(int i){return i&(-i);
}
void pt1(int i,long long v){while(i<=n){tr1[i]=(tr1[i]+v)%mod;i+=lb(i);}
}
long long find1(int i){long long re=0;while(i){re=(re+tr1[i])%mod;i-=lb(i);}return re;
}
void pt2(int i,long long v){while(i<=n){tr2[i]=(tr2[i]+v)%mod;i+=lb(i);}
}
long long find2(int i){long long re=0;while(i){re=(re+tr2[i])%mod;i-=lb(i);}return re;
}
void build(int k,int l,int r){s[k]=hv[k]=ly[k]=0;if(l==r) return;int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);
}
void down(int k){s[lc]=(s[lc]+hv[lc]*ly[k])%mod;s[rc]=(s[rc]+hv[rc]*ly[k])%mod;ly[lc]=(ly[lc]+ly[k])%mod;ly[rc]=(ly[rc]+ly[k])%mod;ly[k]=0;
}
void ch(int k,int l,int r,int x,long long y){if(l==r&&l==x){hv[k]=y;s[k]=ly[k]=0;return;}if(ly[k]) down(k);int mid=l+r>>1;if(x<=mid) ch(lc,l,mid,x,y);else ch(rc,mid+1,r,x,y);hv[k]=(hv[lc]+hv[rc])%mod;s[k]=(s[lc]+s[rc])%mod;
}
void ts(int k,int l,int r,int x,int y,long long v){if(l>=x&&r<=y){ly[k]=(ly[k]+v)%mod;s[k]=(s[k]+v*hv[k])%mod;return;}if(ly[k]) down(k);int mid=l+r>>1;if(x<=mid) ts(lc,l,mid,x,y,v);if(y>mid) ts(rc,mid+1,r,x,y,v);s[k]=(s[lc]+s[rc])%mod;
}
long long find(int k,int l,int r,int x,int y){if(l>=x&&r<=y) return s[k];if(ly[k]) down(k);int mid=l+r>>1;long long re=0;if(x<=mid) re=(re+find(lc,l,mid,x,y))%mod;if(y>mid) re=(re+find(rc,mid+1,r,x,y))%mod;return re;
}
long long gt(){long long re=0;build(1,1,n);for(int i=1;i<=n;i++){re=(re+find(1,1,n,1,p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;ts(1,1,n,p[i],n,p[i]);ch(1,1,n,p[i],i);}return re;
}
long long gt1(){long long re=0;for(int i=1;i<=n;i++){re=(re+1ll*i*(n-i+1)%mod*p[i]%mod*(n-p[i]+1)%mod)%mod;}return re;
}
long long gt2(){long long re=0;for(int i=1;i<=n;i++){re=(re+find1(p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;pt1(p[i],1ll*i*p[i]%mod);}for(int i=1;i<=n;i++){tr1[i]=0;if(i<n-i+1) swap(p[i],p[n-i+1]);}for(int i=1;i<=n;i++){re=(re+find1(p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;pt1(p[i],1ll*i*p[i]%mod);}for(int i=1;i<=n;i++){tr1[i]=0;if(i<n-i+1) swap(p[i],p[n-i+1]);}return re;
}
long long gt3(){long long re=0;for(int i=1;i<=n;i++){long long now=find1(p[i]);pt1(p[i],1ll*i*p[i]%mod);re=(re+find2(p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;pt2(p[i],now);}for(int i=1;i<=n;i++){tr1[i]=tr2[i]=0;if(i<n-i+1) swap(p[i],p[n-i+1]);}for(int i=1;i<=n;i++){long long now=find1(p[i]);pt1(p[i],1ll*i*p[i]%mod);re=(re+find2(p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;pt2(p[i],now);}for(int i=1;i<=n;i++){tr1[i]=tr2[i]=0;if(i<n-i+1) swap(p[i],p[n-i+1]);}re=(re+gt())%mod;for(int i=1;i<=n;i++)if(i<n-i+1) swap(p[i],p[n-i+1]);re=(re+gt())%mod;for(int i=1;i<=n;i++)p[i]=n-p[i]+1;re=(re+gt())%mod;for(int i=1;i<=n;i++)if(i<n-i+1) swap(p[i],p[n-i+1]);re=(re+gt())%mod;return re;
}
int main()
{freopen("points.in","r",stdin);freopen("points.out","w",stdout);scanf("%d%d",&n,&K);for(int i=1;i<=n;i++){scanf("%d",&p[i]);}if(K==1) printf("%lld",gt1());else if(K==2)  printf("%lld",(gt1()+2*gt2())%mod);else{printf("%lld",(gt1()+6*gt2()+6*gt3())%mod);}return 0;
}

相关文章:

2023NOIP A层联测6 数点

题目大意 给你一个排列 p p p&#xff0c;对于每一个 i i i&#xff0c;我们在平面上&#xff0c;放置一个点 ( i , p i ) (i,p_i) (i,pi​)。对于坐标上下限都在 1 ∼ n 1\sim n 1∼n内的全体 ( n ( n 1 ) 2 ) 2 (\frac{n(n1)}{2})^2 (2n(n1)​)2矩形&#xff0c;求每个矩形…...

Jmeter 链接MySQL测试

1.环境部署 1.1官网下载MySQL Connector https://dev.mysql.com/downloads/connector/j/ 1.2 解压后&#xff0c;将jar放到jmeter/lib目录下 1.3 在测试计划中添加引用 2.脚本设置 2.1设置JDBC Connection Configuration 先添加一个setUp线程中&#xff0c;在setUp中添加“…...

jwt的了解和使用以及大致代码分析

jwt简介 以下介绍来自官网&#xff08;https://jwt.io/&#xff09; SON Web 令牌 &#xff08;JWT&#xff09; 是一种开放标准 &#xff08;RFC 7519&#xff09;&#xff0c;它定义了一种紧凑且独立的方式&#xff0c;用于在各方之间以 JSON 对象的形式安全地传输信息。此信…...

uniapp中videojs、renderjs的使用

在uniapp中使用了某些前端库或iframe&#xff0c;需要操作这些库中的dom的时候&#xff0c; 而uni上又没有document等基础对象。也就无法操作这些dom去实现一些交互逻辑&#xff0c;那么&#xff0c;涉及到这些的前端类库就无法使用&#xff0c;例如html2、canvas、image、vide…...

AIGC AI绘画 Midjourney 参数大全详细列表

AIGC ChatGPT 职场案例 AI 绘画 与 短视频制作, Power BI 商业智能 68集, 数据库Mysql8.0 54集 数据库Oracle21C 142集, Office 2021实战, Python 数据分析, ETL Informatica 案例实战 Excel 2021实操,函数大全,图表大全,大屏可视化制作 加技巧500集 数据分析可视化T…...

安装hadoop,并配置hue

0、说明 对于大数据学习的初始阶段&#xff0c;我也曾尝试搭建相应的集群环境。通过搭建环境了解组件的一些功能、配置、原理。 在实际学习过程中&#xff0c;我更多的还是使用docker来快速搭建环境。 这里记录一下我搭建hadoop的过程。 1、下载hadoop 下载地址&#xff1a;…...

23种经典设计模式:单例模式篇(C++)

前言&#xff1a; 博主将从此篇单例模式开始逐一分享23种经典设计模式&#xff0c;并结合C为大家展示实际应用。内容将持续更新&#xff0c;希望大家持续关注与支持。 什么是单例模式&#xff1f; 单例模式是设计模式的一种&#xff08;属于创建型模式 (Creational Pa…...

ros中对move_base的调用

move_base包中自带costmap2d, global planner 等功能 也可以直接调用其中make_plan进行路径规划 #include "geometry_msgs/PoseStamped.h" #includde "nav_msgs/GetPlan.h"void fillPathRequest(nav_msgs::GetPlan::Request &request, float start_x…...

Git从本地库撤销已经添加的文件或目录

场景 在提交时, 误将一个目录添加到了暂存区, 而且commit 了本地库,同批次commit 的还有其他需要提交的文件。 commit 之后发现这个目录下所有的文件都不需要提交, 现在需要撤销这个提交, 使这个目录不被push到远端库。 这里以远端服务器github 为例,在Git GUI下看到的…...

百度SEO优化的特点(方式及排名诀窍详解)

百度SEO优化的特点介绍&#xff1a; 百度SEO优化是指对网站进行优化&#xff0c;使其在百度搜索引擎中获得更好的排名&#xff0c;进而获取更多的流量和用户。百度SEO优化的特点是综合性强、效果持久、成本低廉、投资回报高。百度的搜索算法不断更新&#xff0c;所以长期稳定的…...

Gin 文件上传操作(单/多文件操作)

参考地址: 单文件 | Gin Web Framework (gin-gonic.com)https://gin-gonic.com/zh-cn/docs/examples/upload-file/single-file/ 单文件 官方案例: func main() {router := gin.Default()// 为 multipart forms 设置较低的内存限制 (默认是 32 MiB)router.MaxMultipartMem…...

分类预测 | MATLAB实现KOA-CNN-LSTM开普勒算法优化卷积长短期记忆神经网络数据分类预测

分类预测 | MATLAB实现KOA-CNN-LSTM开普勒算法优化卷积长短期记忆神经网络数据分类预测 目录 分类预测 | MATLAB实现KOA-CNN-LSTM开普勒算法优化卷积长短期记忆神经网络数据分类预测分类效果基本描述程序设计参考资料 分类效果 基本描述 1.MATLAB实现KOA-CNN-LSTM开普勒算法优化…...

Qt应用开发(基础篇)——列表视图 QListView

一、前言 QListView类继承于QAbstractItemView类&#xff0c;提供了一个列表或者图标视图的模型。 视图基类 QAbstractItemView QListView效果相当于Windows文件夹右键->查看->图标和列表&#xff0c;使用setViewMode()设置视图模式&#xff0c;并且提供setIconSize()函数…...

vue-6

一、声明式导航-导航链接 1.需求 实现导航高亮效果 如果使用a标签进行跳转的话&#xff0c;需要给当前跳转的导航加样式&#xff0c;同时要移除上一个a标签的样式&#xff0c;太麻烦&#xff01;&#xff01;&#xff01; 2.解决方案 vue-router 提供了一个全局组件 router…...

温度在线检测技术在电力电缆线路的应用

在电力电缆的日常运行检测中&#xff0c;针对电缆温度的状况&#xff0c;所采用的电力温度在线检测技术也得到了大范围的普及。电网系统中&#xff0c;其单位时间内可输送的电力能源受到其温度的变化影响。因此&#xff0c;采用更有效的方式实时检测电缆系统运行温度&#xff0…...

2023年中国自动化微生物样本处理系统竞争现状及行业市场规模分析[图]

微生物检测能够对感染性疾病的病原体或者代谢物进行检测分析&#xff0c;是IVD的细分领域之一。2022年中国体外诊断市场规模1424亿元。 2015-2022年中国体外诊断市场规模 资料来源&#xff1a;共研产业咨询&#xff08;共研网&#xff09; 微生物检测由于样本类型多样&#xf…...

硬链接和软连接的区别

软链接&#xff08;也称为软连接或符号链接&#xff09;是一种特殊的文件&#xff0c;其内容是另一个文件的路径。当你使用软链接时&#xff0c;实际上是在操作另一个文件。软链接的优点是它可以跨文件系统使用&#xff0c;因此可以跨分区或磁盘链接文件。此外&#xff0c;软链…...

保护隐私与增强网络安全之网络代理技术

目录 前言 一、网络代理技术原理 二、网络代理技术类型 1. HTTP代理 2. SOCKS代理 3. DNS代理 4. 加密代理 5. 反向代理 三、网络代理技术应用 1. 加速网络访问速度 2. 绕过网络限制 3. 保护个人隐私 4. 节省带宽 5. 改善网络安全 四、网络代理技术优缺点 网络…...

【每日一题】CF1680C. Binary String | 双指针 | 简单

题目内容 原题链接 给定一个长度为 n n n 的 01 01 01 字符串&#xff0c;对于一个子串 s u b sub sub &#xff0c;子串内部的 0 0 0 的数量为 x x x &#xff0c;子串以外的 1 1 1 的数量为 y y y &#xff0c;子串的代价为 m a x ( x , y ) max(x, y) max(x,y) &…...

10.selenium进阶

文章目录 1、嵌套网页1、1 什么是嵌套页面1、2 selenium获取嵌套页面的数据 2、执行JavaScript代码3、鼠标动作链4、selenium键盘事件5、其他方法5、1 选择下拉框5、2 弹窗的处理 6、selenium设置无头模式7、selenium应对检测小结 1、嵌套网页 ​ 在前端开发中如果有这么一个需…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...