#C241105E. ABC378E - Mod Sigma Problem

标签（Label）

树状数组
推式子

网址（Website）

E - Mod Sigma Problem (atcoder.jp)

题目（Problem）

问题陈述

给你一个由 $N$ 个非负整数组成的序列 $A = (A_1, A_2, \dots, A_N)$ 和一个正整数 $M$ 。

求下列数值：

$$
\sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right).
$$

这里， $X \mathbin{\mathrm{mod}} M$ 表示非负整数 $X$ 除以 $M$ 的余数。

Constraints

$1 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
$0 \leq A_i \leq 10^9$

输入

输入内容由标准输入法提供，格式如下

N M
A1 A2 ... AN

输出

打印答案。

输入样本 1

3 4
2 5 0

样本输出 1

$A_1 \mathbin{\mathrm{mod}} M = 2$
$(A_1+A_2) \mathbin{\mathrm{mod}} M = 3$
$(A_1+A_2+A_3) \mathbin{\mathrm{mod}} M = 3$
$A_2 \mathbin{\mathrm{mod}} M = 1$
$(A_2+A_3) \mathbin{\mathrm{mod}} M = 1$
$A_3 \mathbin{\mathrm{mod}} M = 0$

答案就是这些值的和 $10$ 。注意，外层和没有取模 $M$ 。

输入样本 2

10 100
320 578 244 604 145 839 156 857 556 400

输出示例 2

题解（Solution）

推式子：把原式转化为前缀和来看，前缀和取 $\text{mod}$ 之后，如果相减为负数，就加上一个 $\text{mod}$ ，式子中的 $x$ 表示的就是满足 $\sum_{1\le l\le r}\left(S_{l-1}> S_{r}\right) $ 的个数。

$\sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right)\\=\sum_{1\le r\le N}\left(\sum_{1\le l\le r}\left(S_r-S_{l-1}\right)+x\times M\right)\\=\sum_{1\le r\le N}\left(r\times S_r-\sum_{1\le l\le r}S_{l-1}+x\times M\right)$

容易发现 $\sum_{1\le l\le r}S_{l-1}$ 可以用前缀和算出，$x$ 可以使用树状数组求出 $\sum_{1\le l\le r}\left(S_{l-1}>S_{r}\right)$ 的个数。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
//#define ull __int128
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 201234;
bool ST;

struct BIT{
	int c[N],n;inline void init(int siz){n=siz;fill(c,c+n+1,0);}
	inline int lbt(int x){return x&-x;}
	void update(int x,int k){for(int i=x;i<=n;i+=lbt(i))c[i]+=k;}
	int ask(int x){int res=0;for(int i=x;i;i-=lbt(i))res+=c[i];return res;}
	inline int sum(int l,int r){return ask(r)-ask(l-1);}
}B;

int a[N],b[N],c[N],d[N];
int n,mod,ans;

void Solve(){
	n=rd(),mod=rd();For(i,1,n)a[i]=rd();
	For(i,1,n) b[i]=(b[i-1]+a[i])%mod;
	For(i,1,n) c[i]=(c[i-1]+b[i]);
	B.init(mod+5);
	For(r,1,n){
		ans += r*b[r] - c[r-1] + B.sum(b[r]+2,mod)*mod;
		B.update(b[r]+1,1);
	}printf("%lld\n",(int)ans);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1;double Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}