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

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

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

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

問題へのリンク

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

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) が成立する。