競プロの問題紹介001 ABC164 Multiple of 2019

D - Multiple of 2019

文字列Sのi～j文字目を10進としてみる場合、その数字が2019で割り切れるi,jの組み合わせを答えよ。

・10進の仕方

文字列の部分文字列を10進数にしないといけませんが、|S|<=200000なので単純にやるとオーバーフローします。
多倍長なら入りますが、O(桁数)かかるため他にかける処理時間が足りなくなり厳しそうです。

☆Sをi文字目から見ていくことを考えます。
　ex.1817181712114　i=3
　i=3,j=3　1
　i=3,j=4　17
　i=3,j=5　171
　...
　jを増やすたびに、*10+S[j]されています。(実際は文字列なのでASCIIコードの変換が必要)
　ここで、この問題では2019で割り切れるか=mod 2019が0になるかが重要です。jを増やしたときの演算は+と*のみなので、逐次modを取っても答えは変わりません(/以外は逐次modが取れます)
　なので、i,jの値=(i,j-1の値*10+S[j])%2019と更新し、i,jの値が0になればカウントを増やすと考えられそうです。

☆i,jを全パターン調べるとO(|S|^2)でアウトです。
　i,jの値はmod 2019する関係上、高々2019通りの値(0～2018)のどれかに収まります。なので、dpで値を管理しながら見ていけばO(|S|)で計算できそうです。
　ex.1817181712114
　i=1　初めの1を記録　(1)
　i=2　初めの8を記録、1*10+8=18を記録　(8,18)
　i=3　初めの1を記録、8*10+1=81を記録、18*10+1を記録　(1,81,181)
　...

#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
   int dp[2][2019]={{0}};
   string S;
   cin>>S;
   int c=0;
   for(int i=0;i<S.size();i++){
       int n=S[i]-'0';
       for(int j=0;j<2019;j++){
           if(j==0||dp[0][j]!=0){
               //cout<<j<<","<<j*10+n<<","<<dp[0][j]+(j==0)<<endl;
               dp[1][(j*10+n)%2019]+=dp[0][j]+(j==0);
           }
       }
       c+=dp[1][0];
       for(int j=0;j<2019;j++){
           dp[0][j]=dp[1][j];
           dp[1][j]=0;
       }
   }
   cout<<c<<endl;
}

AtcoderProblemによると、水下位diffでした。
中々難しいと思うのですが...。