[AtCoder] ABC 164 D – Multiple of 2019
問題
方針
\( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません