Divisible Substring
考えたこと
- 愚直解
- 間に合わない
- 高速化も思いつかない
- 法則性がある？
- 入力3を見ると、Sがすごい大きい数値なのに答えの数値があまりにも小さい（名推理）
- なんか法則性があって計算式を立てれば答え出るんじゃね？（頭良さそう）
- 無理だね（頭悪かった）
- むりだなぁ。かなしいなぁ
- 自分の回答→コード
解法までの流れ
- つかみどころがなさそうなので、とりあえず求めたいものを式にする
- [$S_l, S_0]$の範囲を$U_l$という記号で置き換える
- すると、区間[l, r]の数値は$\frac{U_l - U_{r+1}}{10^r}$という式で表せる
- よって、今回求めたいものは$\frac{U_l - U_{r+1}}{10^r} \equiv 0\ (mod\ P)$となるような区間[l, r]の個数となる
2 $10^r$とPが互いに素ではない場合を考える
- modの除算は、分母とPが互いに素でないとできないので、この場合を考える
- これは、Pが2か5のときに互いに素ではなくなる
- 数値を桁ごとに左から見ていく
- そして、その数値の一の位がPで割れるかを判定することで$O(N)$で答えが求まる
3 $10^r$とPが互いに素である場合を考える
- $\frac{U_l - U_{r+1}}{10^r} \equiv 0\ (mod\ P)$ → $U_l - U_{r+1} \equiv 0\ (mod\ P)$ →$U_l \equiv U_{r+1}\ (mod\ P)$と式変形をする
- つまり、$U_l \equiv U_{r+1}\ (mod\ P)$となるような区間[l, r]の個数を数える問題を考えればいい
- これは両端の数値がわかれば条件に当てはまるかが判定できるということを意味するので、計算量を減らす手がかりになりそう。
- $1253 \equiv 1000+200+50+3\ (mod\ P)$みたいなことができるから、各桁のmodをあらかじめとっておく
- そして、すべての区間[l, r]について足し合わせて判定することで答えが求まる。しかしこれは$O(N^2)$
- なので、累積和を用いる
- そして、$U_l \equiv U_{r+1}\ (mod\ P)$を判定することで$O(N \log N)$で答えが求まる
コード
#include <bits/stdc++.h>
using namespace std;
int N, P;
string S;
int main() {
cin >> N >> P >> S;
// 例外処理
if (P == 2 or P == 5) {
long long ans = 0;
for (int r = 0; r < N; r++) {
if ((S[r] - '0') % P == 0) {
ans += r + 1;
}
}
cout << ans << endl;
return 0;
}
// 各桁ごとにmodを求める
vector<int> s(N+1);
int ten = 1;
for (int i = N-1; i >= 0; i--) {
int num = (S[i] - '0') * ten;
s[i] = num % P;
ten *= 10;
ten %= P;
}
// 累積和を求める
for (int i = N-1; i >= 0; i--) {
s[i] += s[i+1];
s[i] %= P;
}
// 両端の数値を判定して答えを求めていく
long long ans = 0;
map<int, int> mp;
mp[0] = 1;
for (int i = N-1; i >= 0; i--) {
ans += mp[s[i]];
mp[s[i]]++;
}
cout << ans << endl;
return 0;
}
感想
- よくわかんなかったら、求めたいものを式にすると良さそう（それが普通なのかもしれんけど普段やってない）
- 区間の問題は累積和を考えるといい（ってすぬけさんが言ってた）
- あまりの性質みたいなのをあまりわかってなかったなーって思った（ギャグではない）
- ばちゃで参加したんだけど、その時の順位が190位くらいで、「お！調子ええやん！」って思ったけどバチャ内の順位で泣いた（コンテスト中の人も反映されると思ってた）