[AtCoder] ABC 164 D – Multiple of 2019

2020年12月14日

問題

方針

\( 12114 \) は \( 12114 = 2019 \times 6 \) なので \( 2019 \) の倍数です。次に、\( 1211472\) という文字列を考えると、\( 12114 \) という文字列があるので、\( 2019 \) の倍数となる部分文字列があることが分かります。ここで、

\[ 1211400 = 1211472 – 72\]

となるので、\( 121472 \bmod 2019 = 72 \) となることに注目します。

剰余の性質

自然数 \( x \) が  \( x \bmod 2019 = 0\) を満たすとき、自然数 \( y\) を用いて、

\[ 10^{y}x \bmod 2019 = 0 \]

となります。

動的計画法

\( S = s_{n-1}s_{n-2}\cdots s_{0} \) とします。

ここで、\( d(i+1) \) を \( S \) の \( i \) 桁目までの数字 \( s_is_{i-1}\cdots s_0\) の \( 2019 \) の剰余とします。

\[ d(i) = s_is_{i-1}\cdots s_0 \bmod 2019 \]

上記は、

\[ d(i+1) = (d(i) + 10^{i}s_{i}) \bmod 2019\]

と計算できます。ここで、\( d(i) = d(j) (i< j) \) となる \( i, j \) について考えます。\( S = 1211472 \) とすると、\( d(2) = d(7)  = 72 \) となります。したがって、\( d(i) \) の頻度を \( a(d(i)) \) とすると、

\[ \sum_{i=0}^{2018} \dfrac{a(i)(a(i) – 1)}{2}\]

が答えになります。また、\( a(0) \) については、 \( s_{i} \cdots s_{0} \bmod 2019 = 0\) という文字列の個数であり、その部分文字列単体で \( 2019 \) の倍数となるので、\( a(0) = 1 \) と初期化してから頻度を数え上げます。

コード

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


int main() {
    string S;
    cin >> S;
    int n = S.length();
    
    if (n < 4) {
        cout << "0\n";
        return 0;
    }
    
    ll dp[n + 1]{};
    int k = 1;
    ll a[2019]{};
    a[0] = 1;
    for (int i = 0; i < n; i++) {
        int j = n - i - 1;
        int c = S[j] - '0';
        dp[i + 1] = (dp[i] + c * k) % 2019;
        k = (k * 10) % 2019;
        a[dp[i + 1]]++;
    }
    ll ans = 0;
    for (int i = 0; i < 2019; i++) {
        ans += (a[i] * (a[i] - 1)) / 2;
    }
    cout << ans << "\n";
    return 0;
}