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