首页 > 其他分享 >ABC378 E 题解

ABC378 E 题解

时间:2024-11-05 20:34:17浏览次数:1  
标签:取模 le 前缀 int 题解 ABC378 MOD

ABC378 E 题解

题意

给定序列 \(A\) ,求 \(\sum_{1\le l\le r\le n}(\sum_{l\le i\le r} A_i\mod M)\)

计算所有区间和取模之后的结果再求和。

注意外层是没有取模的。

如果是外层也要取模的情况,那还是十分好办的,直接贡献法计算每个数字被统计了多少次就可以了。

问题就在于外层没有取模,之前好像也没有做过这种东西,于是就开始各种乱搞了,思路大概就是先算出不取模的结果,然后计算需要取模多少次,最后统一减去若干个 \(MOD\) 。

甚至还用上了 double 这种玩意。、、

分析

转化题意, \([L,R]\) 的区间和,用前缀和来表达就是 \(s_r-s_{l-1}\) ,这样就转化成了两点之差,所以我们要统计的就是所有的两点之差。

如果我们在做前缀和的时候就取模,那么 \(s_r-s_{l-1}\) 便有可能是负数, 但是注意到取模运算是乘法封闭的,是个负数的话 ,加上一个 \(MOD\) 就可以变成正确的值。

可以发现需要加上的 \(MOD\) 数,就是前缀和数组中的逆序对数量。

而 \(\sum s_r-s_{l-1}\) 可以通过二位前缀和快速算出,注意要考虑 \(s_0\) 。

细节

树状数组求逆序对还需要访问 \(0\) 的下标,所以树状数组的整体下标应该左移 \(1\) 。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void re(T &x)
{
	x=0;int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	x*=f;
}
const int N=4e5+10;
int c[N];
int MOD,n;
inline void add(int x,int v)
{
	for(;x<=MOD;x+=(x&-x))c[x]+=v;
}
inline int query(int x)
{
	int ans=0;
	for(;x>=1;x-=(x&-x))ans+=c[x];
	return ans;
}
int s[N],ss[N];
signed main()
{
	re(n),re(MOD);
	for(int i=1;i<=n;++i)
	{
		re(s[i]);
		s[i]+=s[i-1],s[i]%=MOD;
		ss[i]=ss[i-1]+s[i];
	}
	int cnt=0;
	for(int i=n;i>=1;--i)
	{
		if(s[i]>0)cnt+=query(s[i]);
		add(s[i]+1,1);
	}
	int ans=0;
	for(int i=1;i<=n;++i)
		ans+=i*s[i]-ss[i-1];
	cout<<ans+cnt*MOD;
	return 0;
}

Trick

求区间和可以转化成前缀和的差值,这样就简化了问题,变成了两点之差。

标签:取模,le,前缀,int,题解,ABC378,MOD
From: https://www.cnblogs.com/Hanggoash/p/18528743

相关文章

  • 2024强网杯web题解
    PyBlocklyfromflaskimportFlask,request,jsonifyimportreimportunidecodeimportstringimportastimportsysimportosimportsubprocessimportimportlib.utilimportjsonapp=Flask(__name__)app.config['JSON_AS_ASCII']=Falseblacklis......
  • 2024newstarweb题解
    w1headach3会赢吗源码flag碎片X1:ZmxhZ3tXQTB3再次查看源码flag碎片X2:IV95NF9yM2Fs第三个页面也是直接查看源码直接改源码flag碎片X3:MXlfR3I0c1B下一个页面直接禁用jsflag碎片X4:fSkpKcyF9ZmxhZ3tXQTB3IV95NF9yM2FsMXlfR3I0c1BfSkpKcyF9base64解码即......
  • WPF程序弹出页中按钮在触摸屏(电容屏)上点击事件需要点十次才能触发的问题解决方法
    一、事件背景介绍1.功能简述:主页面是一个DataGrid列表,点击DataGrid行,弹出子页面;子页面根据数据加载多个Button按钮,如下图,就是这个页面中的按钮,在触摸屏上触摸点击,需要点击十次才能成功,使用鼠标点击一下就能成功。 主要代码如下://WPF前端<DataGridx:Name="scanDtl......
  • P11236 「KTSC 2024 R1」水果游戏 题解
    很有意思的一道题。思路首先将相邻一样的数合并,每个元素变成一个二元组,表示数与出现次数。考虑什么时候不能合并。我们发现假如充分合并后,现在有连续的三个数\(x_1,x_2,x_3\),以及他们各自的出现次数\(y_1,y_2,y_3\)。如果\(x_1>x_2,x_3>x_2\)。我们想要合并这三个,必须要......
  • xss-labs题解
    xss—labsxss—labslevel1(GET型)level2(闭合)level3(htmlspecialchars绕过)level4(左右尖括号过滤)level5(a标签法)level6(大小写绕过)level7(双写绕过)level8(利用href自动Unicode解码特性)level9(注释绕过后端判断)xss—labs题目链接BUUCTF在线评测题目源码xss-lab/lev......
  • CSP-J2024题解
    前言J组本来可以AK的,但是对于DP的敏感度太低了,导致T4赛时没有往DP上面想。正片T1:扑克牌题目描述小P从同学小Q那儿借来一副\(n\)张牌的扑克牌。本题中我们不考虑大小王,此时每张牌具有两个属性:花色和点数。花色共有\(4\)种:方片、草花、红桃和黑桃。点数共......
  • 题解 P11231【[CSP-S 2024] 决斗】
    题目描述今天是小Q的生日,他得到了\(n\)张卡牌作为礼物。这些卡牌属于火爆的“决斗怪兽”,其中,第\(i\)张卡代表一只攻击力为\(r_i\),防御力也为\(r_i\)的怪兽。一场游戏分为若干回合。每回合,小Q会选择某只怪兽\(i\)以及另一只怪兽\(j(i\neqj)\),并让怪兽\(i\)向怪......
  • 题解 P11232【[CSP-S 2024] 超速检测】
    题目描述小D新入职了某国的交管部门,他的第一个任务是负责国家的一条长度为\(L\)的南北主干道的车辆超速检测。为了考考小D,上司首先需要他解决一个简化的场景。这个周末,主干道上预计出现\(n\)辆车,其中第\(i\)辆车从主干道上距离最南端\(d_i\)的位置驶入,以\(v_i\)的......
  • 题解 P11233【[CSP-S 2024] 染色】
    题目描述给定一个长度为\(n\)的正整数数组\(A\),其中所有数从左至右排成一排。你需要将\(A\)中的每个数染成红色或蓝色之一,然后按如下方式计算最终得分:设\(C\)为长度为\(n\)的整数数组,对于\(A\)中的每个数\(A_i\)(\(1\leqi\leqn\)):如果\(A_i\)左侧没有与其同......
  • 牛客周赛 Round 66 题解
    牛客周赛Round66题解牛客周赛Round66A-小苯吃糖果_牛客周赛Round66#include<bits/stdc++.h>#defineendl'\n'usingnamespacestd;inta[5];voidsolve(){ for(inti=1;i<=3;i++)cin>>a[i]; sort(a+1,a+4); intans=max(a[1]+a[2],a[3]); cout<......