まさかの既出！！！しかも割と最近の ABC-E！！！

問題概要

$1$ から $9$ までの数字のみからなる文字列 $S$ が与えられる。

$S$ の連続する区間であって、 $2019$ の倍数であるものが何個あるのかを求めよ。

制約

$1 \le |S| \le 2 \times 10^{5}$

考えたこと

実は完全にマジで既出だった！！！！！
ただし ABC 157-E では、「2019」のところが一般的な素数 $P$ なので、ちょっとだけコーナーケースを含んで難しくなってる。今回の問題では、 $P$ が $2019$ なので、少しだけ簡単になってる。

drken1215.hatenablog.com

さて、そもそもこの問題のように、「連続する区間」についての問題では、"累積和的なもの" をとるのが定石である。通常、累積和は左側から考えるケースが多いけど、今回は右側から考える。

たとえば 8 桁の整数 S = 41817134 について考えてみる。これの部分文字列を、次のような 9 個の整数の差分として考えることにする。

s[0] = 0
s[1] = 4
s[2] = 34
s[3] = 134
s[4] = 7134
s[5] = 17134
s[6] = 817314
s[7] = 1817134
s[8] = 41817134

たとえば、部分文字列の一つである 18171 は、次にように考えることができる。

18171 は、右から 7 文字分 (s[7] = 1817134) から、右から 2 文字分 (s[2] = 34) を除去したものである
それを踏まえて s[7] - s[2] を計算すると、1817100 となる
これは 18171 を 100 倍した値である

このように、「該当する部分文字列に 10 を何回かかけると、累積和 s の差分で表せる」という状態になっていることがわかる。

区間が 2019 で割りきれることを、累積和の言葉で

さらにさらに、該当する部分文字列が 2019 の倍数ということは、

18171 は 2019 の倍数なので
s[7] - s[2] = 1817100 も 2019 の倍数である
よって、s[7] と s[2] を 2019 で割ったあまりは等しい

という風に解釈できる！！！つまり、次のようになる！

S の連続する区間が、右から a 文字分から、右から b 文字分を取り除いたものであるとき
その区間の整数が 2019 の倍数になるということは、s[a] と s[b] を 2019 で割ったあまりが等しい

注意点として、「連続区間が 2019 の倍数なら、s[a] と s[b] を 2019 で割ったあまりが等しい」というのは間違いなく成り立つが、逆に「s[a] と s[b] を 2019 で割ったあまりが等しいならば、該当する連続区間が 2019 の倍数」というのが成り立つのか心配になる。

事実、既出となった ABC 157 E では、これが成り立たないケースがあるのだ。でも今回は成り立つ。その理由は 2019 と 10 が互いに素だからなのだけど、詳しくは該当問題の記事にて。

具体的な解法へ

以上の考察から、次のように解ける。

N 文字の文字列 S から、長さ N+1 の累積和 s[0], s[1], ..., s[N] を作る
これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

計算量は、 $O(N)$ 。

#include <bits/stdc++.h>
using namespace std;

long long solve(const string &S) {
    int N = S.size();
    vector<long long> val(2019, 0);
    long long fac = 1;
    long long cur = 0;
    val[cur]++;
    for (int i = 0; i < N; ++i) {
        long long add = S[N-1-i] - '0';
        cur = (cur + fac * add) % 2019;
        fac = (fac * 10) % 2019;
        val[cur]++;
    }
    long long res = 0;
    for (int i = 0; i < val.size(); ++i) {
        res += val[i] * (val[i] - 1) / 2;
    }
    return res;
}

int main() {
    string S;
    cin >> S;
    cout << solve(S) << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 164 D - Multiple of 2019 (水色, 400 点)

問題概要

制約

考えたこと

区間が 2019 で割りきれることを、累積和の言葉で

具体的な解法へ