ABC105-D: Candy Distribution

余りの累積和

累積和

概要

NN要素の配列ANA_N(N≤105N \leq 10^5)に ∑i=lrAi%m=0\sum^{r}_{i = l} A_i \% m = 0を満たす(l,r)(l, r)ペアはいくつあるか.

連続区間なので, 累積和を用いて区間(l,r)(l, r)の和の余りを表せないか考える.
Sk=∑i=0kAiS_k = \sum^{k}_{i=0} A_i とすると, Si%mS_i \% mで表せる. 区間(l,r)(l, r)の場合には, (S(r)−S(l))%m\left(S(r) - S(l)\right) \% mとなる.
ただ, 上式だと余りを求める際にS(r),S(l)S(r), S(l)両端が必要になるので, ２重ループになってしまい, まだ計算量を削る必要がある.
これは S(r)−S(l)%m==0  ⟺  S(r)≡S(l) (mod m)S(r) - S(l) \% m == 0 \iff S(r) \equiv S(l) \ (mod \: m)と変形できるので, S(i)%mS(i) \% mを累積和として持てばO(N)O(N)で計算できる.

解答

fn main() {
    let (n, m) = {
        let i = read::<usize>();
        (i[0], i[1])
    };

    let an = read::<usize>();
    let mut rem = HashMap::new();
    let mut cs = vec![0; n];
    cs[0] = an[0] % m;
    *rem.entry(cs[0]).or_insert(0) += 1;

    for i in 1..n {
        cs[i] = (cs[i - 1] + an[i]) % m;
        *rem.entry(cs[i]).or_insert(0) += 1;
    }

    let ans = rem.iter()
        .map(|(_, &num)| if num >= 2 { ncr(num, 2) } else { 0 })
        .sum::<usize>();

    println!("{}", ans + rem.get(&0).unwrap_or(&0));
}

まとめ

∑i=lrAi%m=0  ⟺  (S(r)−S(l)%m=0  ⟺  S(r)≡S(l) (mod m)\sum^{r}_{i = l} A_i \% m = 0 \iff (S(r) - S(l) \% m = 0 \iff S(r) \equiv S(l) \ (mod \: m)

Commits

2021-01-30 22:18:1735b550aecopy md
commit 35b550ae83af4efaeadf33471c8ca8a32c1079c8
Author: koka &&gt;
Date:   Sat Jan 30 22:18:17 2021 +0900

  copy md

diff --git a/_posts/2019-03-15-candy-distribution.md b/_posts/2019-03-15-candy-distribution.md
new file mode 100644
index 0000000..aa1bd53
--- /dev/null
+++ b/_posts/2019-03-15-candy-distribution.md
@@ -0,0 +1,54 @@
+---
+title: 'ABC105-D: Candy Distribution'
+date: 2019-03-15
+categories:
+- Competitive Programming
+tags:
+- 累積和
+description: 余りの累積和
+---
+
+## 概要
+$N$要素の配列$A_N$($N \leq 10^5$)に
+$\sum^{r}_{i = l} A_i \% m = 0$を満たす$(l, r)$ペアはいくつあるか.  
+
+---
+
+連続区間なので, 累積和を用いて区間$(l, r)$の和の余りを表せないか考える.  
+$S_k = \sum^{k}_{i=0} A_i$ とすると, $S_i \% m$で表せる.
+区間$(l, r)$の場合には, $\left(S(r) - S(l)\right) \% m$となる.  
+ただ, 上式だと余りを求める際に$S(r), S(l)$両端が必要になるので, ２重ループになってしまい, まだ計算量を削る必要がある.  
+これは $S(r) - S(l) \% m == 0 \iff S(r) \equiv S(l) \ (mod \: m)$と変形できるので, $S(i) \% m$を累積和として持てば$O(N)$で計算できる.  
+
+
+## 解答
+
+\```rust
+fn main() {
+    let (n, m) = {
+        let i = read::&lt;usize&gt;();
+        (i[0], i[1])
+    };
+
+    let an = read::&lt;usize&gt;();
+    let mut rem = HashMap::new();
+    let mut cs = vec![0; n];
+    cs[0] = an[0] % m;
+    *rem.entry(cs[0]).or_insert(0) += 1;
+
+    for i in 1..n {
+        cs[i] = (cs[i - 1] + an[i]) % m;
+        *rem.entry(cs[i]).or_insert(0) += 1;
+    }
+
+    let ans = rem.iter()
+        .map(|(_, &num)| if num &gt;= 2 { ncr(num, 2) } else { 0 })
+        .sum::&lt;usize&gt;();
+
+    println!("{}", ans + rem.get(&0).unwrap_or(&0));
+}
+\```
+
+
+## まとめ
+$\sum^{r}_{i = l} A_i \% m = 0 \iff (S(r) - S(l) \% m = 0 \iff S(r) \equiv S(l) \ (mod \: m)$