2020-03-08

AtCoder ABC 158 E - Divisible Substring (青色, 500 点)

AtCoder AtCoder500点 ABC-E 集計処理数学(整数問題) 互いに素累積和コーナーケース解空間:O(N^2)通りの選択肢 nC2 青色diff Zero-Sum Ranges 区間連続部分列を扱う問題数え上げ問題典型要素を詰め合わせた教育的問題

こういう問題を求めてた！！

問題へのリンク

類題として、こんなのがある。

drken1215.hatenablog.com

問題概要

長さ $N$ の、各文字が '0'〜'9' のいずれかとなっている文字列 $S$ と、素数 $P$ が与えられる。

$S$ の空でない連続する区間であって、その整数が $P$ で割り切れるものが何個あるかを求めよ。

制約

$N \le 2 \times 10^{5}$
$P$ は $2 \le P \le 10^{4}$ を満たす素数

考えたこと

文字列の右側から $v$ 個分からなる整数を $a_{v}$ とおくことにする。たとえば、

S = 1533032

であれば、

$a_{0}$ = 0
$a_{1}$ = 2
$a_{2}$ = 32
$a_{3}$ = 32 ("032")
$a_{4}$ = 3032

という感じにする。こういう風に「区間に関する問題において、累積和的なものを考える」というのは、Zero-Sum Ranges でもおなじみの考え方！！！！！！！

さて、このとき、S の区間 $\lbrack l, r)$ が条件を満たす条件は

$\frac{a_{l} - a_{r}}{10^{r}} ≡ 0$ $({\rm mod}. P)$

と表せることになる。ここで勢いで両辺に $10^{r}$ をかけて

$a_{l} - a_{r} ≡ 0$ $({\rm mod}. P)$

という風にしてしまいたくなる。この式自体は間違ってない。けど、冷静にならないといけない。この合同式を満たすからといって、元の合同式を満たすとは限らないのだ。

ちなみに、もし仮に「 $a_{l} ≡ a_{r}$ $({\rm mod}. P)$ を満たすような $l, r$ を求めたい」という話に落ちたならば、あとは簡単だ。たとえば S = "152467"、"P = 3" であったら

$a_{0} = 0$
$a_{1} = 7 ≡ 1$
$a_{2} = 67 ≡ 1$
$a_{3} = 467 ≡ 2$
$a_{4} = 2467 ≡ 1$
$a_{5} = 52467 ≡ 0$
$a_{6} = 152467 ≡ 1$

となるので、

$a_{l} ≡ a_{r} ≡ 0$ となるような $l, r$ は、 ${}_{2}{\rm C}_{2} = 1$ 個
$a_{l} ≡ a_{r} ≡ 1$ となるような $l, r$ は、 ${}_{4}{\rm C}_{2} = 6$ 個
$a_{l} ≡ a_{r} ≡ 2$ となるような $l, r$ は、そもそも 2 が 1 回しかないので 0 個

よって答えは、1 + 6+ 0 = 7 個となる。

合同式の式変形について

一般に、 $a$ と $m$ が互いに素であれば、

$x ≡ y$ $({\rm mod}. m)$
⇔ $ax ≡ ay$ $({\rm mod}. m)$

が成立するのだ。一般の場合であっても、

$x ≡ y$ $({\rm mod}. m)$
⇒ $ax ≡ ay$ $({\rm mod}. m)$

は成立する。しかし逆が成り立つとは限らない。たとえば

$x = 3$
$y = 5$

を 10 で割ったあまりは異なるけれど、

$5x = 15 ≡ 5$ $({\rm mod}. 10)$
$5y = 25 ≡ 5$ $({\rm mod}. 10)$

となって、 $5x ≡ 5y$ $({\rm mod}. 10)$ が成立してしまうのだ。でも $a$ と $m$ が互いに素だったら、掛けたり割ったりして大丈夫！！！！！！

一応、一番下で証明を書いてみる。

元の問題に戻り

そういうわけで、これ。

$\frac{a_{l} - a_{r}}{10^{r}} ≡ 0$ $({\rm mod}. P)$

実は $P = 2, 5$ の場合がコーナーケースになっている。この場合は $10^{r}$ と互いに素ではないのだ。

でもそれ以外の素数 $P$ に対しては、 $P$ と $10^{r}$ は互いに素になる。なぜなら $10^{r}$ を素因数分解すると

$10^{r} = 2^{r} \times 5^{r}$

となる。素因数に出てくるのは 2 と 5 のみだ。

P が 2, 5 以外の素数のとき

この場合は安心して、上の合同式の両辺に $10^{r}$ を掛けて良い。そうすると

$a_{l} ≡ a_{r}$ $({\rm mod}. P)$

となる。この場合は、上ですでに述べたように

$a_{i}$ を $P$ で割ったあまりで分類する
各分類ごとにペアの個数を数える

という風にすれば OK。このあたりは、かの有名な下の問題と発想は一緒。

qiita.com

P = 2 のとき

2 の倍数であることは、「下 1 桁が偶数であること」と同値である。よって、区間 [l, r) であって S[r-1] が偶数であるものを数えれば OK。

P = 5 のとき

5 の倍数であることは、「下 1 桁が 0 または 5 であること」と同値である。よって、区間 [l, r) であって S[r-1] が 0 または 5 であるものを数えれば OK。

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

long long N;
string S;
int P;

long long solve() {
    if (P == 2 || P == 5) {
        long long res = 0;
        for (int i = 0; i < N; ++i) if ((S[N-i-1]-'0') % P == 0) res += N-i;
        return res;
    }
    vector<long long> val(P, 0);
    long long tenfactor = 1;
    long long cur = 0;
    val[cur]++;
    for (int i = 0; i < N; ++i) {
        cur = (cur + (S[N-i-1]-'0') * tenfactor) % P;
        tenfactor = (tenfactor * 10) % P;
        val[cur]++;
    }
    long long res = 0;
    for (int p = 0; p < P; ++p) res += val[p] * (val[p] - 1) / 2;
    return res;
}

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

おまけ：「互いに素」の場合の証明

最後に $a$ と $m$ が互いに素であれば、

$x ≡ y$ $({\rm mod}. m)$
⇔ $ax ≡ ay$ $({\rm mod}. m)$

であることを証明しておく。上から下は明らかなので、下から上を示す。
さて、 $ax ≡ ay$ $({\rm mod}. m)$ が成立するということは、

$a(x-y)$ が $m$ で割り切れる

ということになる。 $a$ と $m$ が互いに素なので、

$x-y$ が $m$ で割り切れる

よって $x ≡ y$ $({\rm mod}. m)$ が成立する。

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

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