Loading...

题解 CF993E

check评论:0 条 remove_red_eye浏览量:47 change_historyTags:编程学习笔记
作者 : Decoration date_range日期 : 2019-08-01

题目链接

  • 题目简述

给定一个长度为$n$的序列,和一个数$x$,问对于$k\in[0,n]$,分别有多少区间内正好包含了$k$个小于$x$的数

  • 题目分析

考虑到所有小于$x$的数个数为$k_0$,当前区间内有$k$个小于$x$的数,则该区间左右两区间就有$k_0-k$个数,将$k_0-k$看作指数,这显然是一个卷积,可以$NTT$计算

我们考虑构造多项式$A$和$B$,先从左到右扫一遍,扫到第$i\in[1,n]$个点时,若当前小于$x$的数个数为$cnt$,则$a_{cnt}+1$,再从右向左,同理得到$B$

然后将$A$和$B$卷积即可

不放代码了

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名