牛客练习赛25 C 再编号
2024-08-30 21:54:02
解题思路
我们先来观察一下题目中给出的公式
$$a'_i=(\sum_{j=1}^na_j)-a_i$$
通过这个公式推一下经过再编号后的序列的总和,因为我们推出这个和之后可以进行下一次计算。
$$\sum_{i=1}^na'_i=\sum_{i=1}^n((\sum_{j=1}^na_j)-a_i)$$
变形一下
$$\sum_{i=1}^na'_i=n\times (\sum_{j=1}^na_j)-\sum_{i=1}^na_i$$
$$\sum_{i=1}^na'_i=(n-1)\times \sum_{i=1}^na_i$$
emmmm,这个结论貌似很有用的样子,我们可以通过上面的推导预处理处每一次变化后整个序列的总和。
在观察一下原来的序列,每一次再编号他们的每个数和第一个数的差的绝对值是不变的。并且在奇数次的变化后为$a_1-a_j$,偶数次变化后是$a_j-a_1$。
既然是这样子,那我们就可以再通过之前预处理的总和在处理出每一次改变后的第一个值。通过这个值我们可以$O(1)$的对每一个位置上的数值进行询问。
这样的话总时间复杂度是$O(t)$的
代码看这里
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
#define LL long long
#define mod int(1e9+7)
LL a[],n,m,sum[];
LL ans[][],num;
int main()
{
LL x,t;
scanf("%lld%lld%lld",&n,&m,&a[]);
num=a[];
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
num+=a[i];
sum[i]=a[]-a[i];
}
ans[][]=a[];
for(int i=;i<=;i++)
{
ans[i][]=((num-a[])+*mod)%mod;
a[]=ans[i][];
num=(num*(n-))%mod;
}
for(int i=;i<=m;i++)
{
scanf("%lld%lld",&x,&t);
if(t%!=)printf("%lld\n",(ans[t][]+sum[x]+mod)%mod);
else printf("%lld\n",(ans[t][]-sum[x]+mod)%mod);
}
}
最新文章
- MySQL+Amoeba实现数据库主从复制和读写分离
- win8 VB6打开提示MSCOMCTL.ocx未注册
- 关于HTTP的几种
- Eclipse添加注释简介
- 用命令访问D:\python学习\wendjia教程\aa.py
- 使用iBATIS3.0完成增删改查
- Select的深入应用(2)
- [原创]PostgreSQL Plus Advanced Server监控工具PEM(四)
- pyhton小方法
- 关于 Unity UGUI 中修改 Mask 组件下 Image 等子节点组件的材质无效的问题
- python 命令行参数,以及文件操作
- wind7系统修改host
- Codeforces 712B
- WPF 中的 Pack URI地(资源文件加载)
- 翻译:Identifier Qualifiers标识限定符
- 关于JQ中,新生成的节点on绑定事件失效的解决
- Linux中各个文件的作用
- 这是一个新的开始at this very monment
- paddle——docker实践
- 搜索入门_简单搜索bfs dfs大杂烩
热门文章
- RK3288 6.0 双屏异显,横屏+竖屏【转】
- 学习MAP 地图好地址
- Flask的多app应用,多线程如何体现
- [IOI2005]Riv 河流
- 重装Eclipse 往其中加Python插件时 遇到不能独立运行c c++ python 代码时修改办法:
- Kettle 连接 oracle 报错:could not be found, make sure the &#39;Oracle&#39; driver (jar file) is installed.
- PCB DotNetCore Swagger生成WebAPI文档配置方法
- bzoj 1584: [Usaco2009 Mar]Cleaning Up 打扫卫生【dp】
- bzoj 1770: [Usaco2009 Nov]lights 燈【高斯消元+dfs】
- 思维/构造 HDOJ 5353 Average