【AtCoder】Beginner Contest 378-E.Mod Sigma Problem

题目链接

Problem Statement

You are given a sequence A = ( A 1 , A 2 , … , A N ) A = (A_1, A_2, \dots, A_N) A=(A1​,A2​,…,AN​) of N N N non-negative integers, and a positive integer M M M.

Find the following value:

∑ 1 ≤ l ≤ r ≤ N ( ( ∑ l ≤ i ≤ r A i ) m o d 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). 1≤l≤r≤N∑​((l≤i≤r∑​Ai​)modM).

Here, X m o d M X \mathbin{\mathrm{mod}} M XmodM denotes the remainder when the non-negative integer X X X is divided by M M M.

问题陈述

给你一个由 N N N 个非负整数组成的序列 A = ( A 1 , A 2 , … , A N ) A = (A_1, A_2, \dots, A_N) A=(A1​,A2​,…,AN​)和一个正整数 M M M 。

求下列数值：

∑ 1 ≤ l ≤ r ≤ N ( ( ∑ l ≤ i ≤ r A i ) m o d 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). 1≤l≤r≤N∑​((l≤i≤r∑​Ai​)modM).
这里， X m o d M X \mathbin{\mathrm{mod}} M XmodM 表示非负整数 X X X 除以 M M M 的余数。

Constraints

• 1 ≤ N ≤ 2 × 1 0 5 1 \leq N \leq 2 \times 10^5 1≤N≤2×105
• 1 ≤ M ≤ 2 × 1 0 5 1 \leq M \leq 2 \times 10^5 1≤M≤2×105
• 0 ≤ A i ≤ 1 0 9 0 \leq A_i \leq 10^9 0≤Ai​≤109

Input

The input is given from Standard Input in the following format:

N M
A1 A2 ... AN

Output

Print the answer.

Sample Input 1

3 4
2 5 0

Sample Output 1

10

• A 1 m o d M = 2 A_1 \mathbin{\mathrm{mod}} M = 2 A1​modM=2
• ( A 1 + A 2 ) m o d M = 3 (A_1+A_2) \mathbin{\mathrm{mod}} M = 3 (A1​+A2​)modM=3
• ( A 1 + A 2 + A 3 ) m o d M = 3 (A_1+A_2+A_3) \mathbin{\mathrm{mod}} M = 3 (A1​+A2​+A3​)modM=3
• A 2 m o d M = 1 A_2 \mathbin{\mathrm{mod}} M = 1 A2​modM=1
• ( A 2 + A 3 ) m o d M = 1 (A_2+A_3) \mathbin{\mathrm{mod}} M = 1 (A2​+A3​)modM=1
• A 3 m o d M = 0 A_3 \mathbin{\mathrm{mod}} M = 0 A3​modM=0

The answer is the sum of these values, 10 10 10. Note that the outer sum is not taken modulo M M M.

Sample Input 2

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

Sample Output 2

2736

解法

这道题目着重考察[[树状数组]]，首先我们先从[[前缀和]]出发。

数组中前 i i i 项和为 s [ i ] s[i] s[i] 。

对题目中计算式子进行变化。
∑ l ≤ i ≤ r A i = s [ r ] − s [ l − 1 ] \sum_{l\leq i \leq r} A_i = s[r] - s[l - 1] l≤i≤r∑​Ai​=s[r]−s[l−1]

接下来，考虑对 M M M 取余操作。

( s [ r ] − s [ l − 1 ] )   m o d   M = { s [ r ] − s [ l − 1 ] , s [ r ] ≥ s [ l − 1 ] s [ r ] − s [ l − 1 ] + M , s [ r ] < s [ l − 1 ] (s[r]-s[l-1]) \bmod M=\left\{\begin{array}{ll} s[r]-s[l-1], & s[r] \geq s[l-1] \\ s[r]-s[l-1]+M, & s[r]<s[l-1] \end{array}\right. (s[r]−s[l−1])modM={s[r]−s[l−1],s[r]−s[l−1]+M,​s[r]≥s[l−1]s[r]<s[l−1]​
从上述公式可以看出，加 o r or or 不加 M M M 取决于 s [ r ] s[r] s[r] 与 s [ l − 1 ] s[l - 1] s[l−1] 的大小情况。
这里，我们将 s [ r ] s[r] s[r] 与 s [ l − 1 ] s[l - 1] s[l−1] 的大小情况定义为一个命题。
那么，公式可以改写为：
( s [ r ] − s [ l − 1 ] )   m o d   M = s [ r ] − s [ l − 1 ] + M ∗ [ s [ r ] < s [ l − 1 ] ] (s[r]-s[l-1]) \bmod M=s[r]-s[l-1]+M *[s[r]<s[l-1]] (s[r]−s[l−1])modM=s[r]−s[l−1]+M∗[s[r]<s[l−1]] 将公式带入原题中可得：
∑ 1 ≤ l ≤ r ≤ N ( ( ∑ l ≤ i ≤ r A i ) m o d M ) = ∑ 1 ≤ l ≤ r ≤ N s [ r ] − s [ l − 1 ] + M ∗ [ s [ r ] < s [ l − 1 ] ] = ∑ 1 ≤ l ≤ r ≤ N ( s [ r ] − s [ l − 1 ] ) + ∑ 1 ≤ l ≤ r ≤ N M ∗ [ s [ r ] < s [ l − 1 ] ] = ∑ 1 ≤ l ≤ r ≤ N s [ r ] − ∑ 1 ≤ l ≤ r ≤ N s [ l − 1 ] + M ∑ 1 ≤ l ≤ r ≤ N [ s [ r ] < s [ l − 1 ] ] = ∑ r = 1 n s [ r ] × r − ∑ l = 1 n s [ l − 1 ] × ( n − l + 1 ) + M ∑ 1 ≤ l ≤ r ≤ N [ s [ r ] < s [ l − 1 ] ] \begin{aligned} \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 \leq l \leq r \leq N} s[r]-s[l-1]+M *[s[r]<s[l-1]] \\ & =\sum_{1 \leq l \leq r \leq N}(s[r]-s[l-1])+\sum_{1 \leq l \leq r \leq N} M *[s[r]<s[l-1]] \\ & =\sum_{1 \leq l \leq r \leq N} s[r]-\sum_{1 \leq l \leq r \leq N} s[l-1]+M \sum_{1 \leq l \leq r \leq N}[s[r]<s[l-1]] \\ & =\sum_{r=1}^{n} s[r] \times r-\sum_{l=1}^{n} s[l-1] \times(n-l+1)+M \sum_{1 \leq l \leq r \leq N}[s[r]<s[l-1]] \end{aligned}\\ 1≤l≤r≤N∑​((l≤i≤r∑​Ai​)modM)​=1≤l≤r≤N∑​s[r]−s[l−1]+M∗[s[r]<s[l−1]]=1≤l≤r≤N∑​(s[r]−s[l−1])+1≤l≤r≤N∑​M∗[s[r]<s[l−1]]=1≤l≤r≤N∑​s[r]−1≤l≤r≤N∑​s[l−1]+M1≤l≤r≤N∑​[s[r]<s[l−1]]=r=1∑n​s[r]×r−l=1∑n​s[l−1]×(n−l+1)+M1≤l≤r≤N∑​[s[r]<s[l−1]]​
对于公式最后一行，进行一下解释。

从倒数第二行的公式可以看出来，在范围从 [ 1 , N ] [1, N] [1,N] 之间，我们要计算 s [ r ] s[r] s[r]时，可以看出每个 s [ r ] s[r] s[r]被计算 r r r次，每个 s [ l − 1 ] s[l - 1] s[l−1] 被计算 n − l − 1 n - l - 1 n−l−1 次。所以，倒数第二行公式可以简化为最后一行公式。然后再看一下倒数第二行的最后一个命题， l − 1 l - 1 l−1 是必然小于 r r r 的，但是呢？ s [ r ] < s [ l − 1 ] s[r] < s[l -1] s[r]<s[l−1] ，这种形式很符合逆序对，所以只需要统计逆序对的个数，然后在乘上 M M M 就可以了。

这里，我们已经将公式化为最简了，接下来，看看代码如何编写吧。

typedef long long LL;
int n, m;
int a[N], s[N];

struct BIT{
	#define lowbit(x) ((x) & (-(x)))
	int tree[N];

	void add(int p, int x) {
		++ p;
		while(p < N) {
			tree[p] += x;
			p += lowbit(p);
		}
	}

	int query(int p) {
		++ p;
		if(p <= 0) return 0;

		int res = 0;
		while(p) {
			res += tree[p];
			p -= lowbit(p);
		}
		return res;
	}
}bit;


void solved() {
	/* your code */
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i <= n; i ++) s[i] = (s[i - 1] + a[i]) % m;

	LL ans = 0;
	for (int r = 1; r <= n; r ++) ans += s[r] * r * 1LL;
	for (int l = 1; l <= n; l ++) ans -= s[l - 1] * (n - l + 1) * 1LL;

	LL cnt = 0;
	for (int i = 1; i <= n; i ++) {
		cnt += i - 1 - bit.query(s[i]);
		bit.add(s[i], 1);
	}
	ans += cnt * m * 1LL;						
	cout << ans << endl;
}

总结

本题难度适中，重在考查对于树状数组的使用，这期间我们要简化我们的公式，这是重中之重。