D - Multiple of 2019

Quiz

https://atcoder.jp/contests/abc164/tasks/abc164_d

解法 (editorial)

• 右からi番目までを数字として見て mod 2019した結果を持っておく
• 入力の数字は文字列で受け取り、1桁ずつ処理すれば桁あふれしない
• modの結果が同じ数字のところは、それを組み合わせることでmodの結果を0にできる（下の画像参照）

AC code

https://atcoder.jp/contests/abc164/submissions/12424738

code

// a^b mod p
ll mod_pow(ll a, ll b){
    if(b==0) return 1;
 
    // 肩が奇数
    if(b%2==1){
        return a * mod_pow(a, b-1) % mod;
    }
    else{
        return mod_pow(a*a % mod, b/2) % mod;
    }
}
 
// nC2
ll nCr(ll n, ll r=2){
  if(n==0 || n==1) return 0;
  return n*(n-1)/2;
}
 
int main(){
    // input
    string s;cin>>s;
    ll L = s.size();
 
    VI A(L); // 右からi文字見た時のmod
    A[0] = s[L-1]-'0';
    FOR(i,1,L){
      char c = s[L-1-i];
      ll v = c-'0';
      A[i] = (A[i-1] + mod_pow(10,i) * v) % 2019;
    }
 
    map<ll,ll> mp;
    mp[0]++;
    for(ll a : A) mp[a]++;
 
    ll sum=0;
    for(auto pa : mp){
      ll cnt = pa.second;
      sum += nCr(cnt, 2);
    }
    p(sum);
 
    return 0;
}

• mod_powはなくても解けます。ループごとにx10される値を持っておけばよい(毎回mod 2019も取っておく)
  • 例：https://atcoder.jp/contests/abc164/submissions/12424260
  • これでいう ten という変数

別解

• dp[2019]
• 文字列を左から見つつ、modの結果の場合の数を持つDP
• 計算量 O(2019 x N) ギリギリ通る (C++ or PyPy)
• https://atcoder.jp/contests/abc164/submissions/12425137

// dp[2050][200010]とするとメモリ足りなそうなので配列を再利用する
ll dp0[2050];
ll dp1[2050];

int main(){
    // input
    string s;cin>>s;
    ll L = s.size();

    ll v = s[0] - '0';
    dp0[v] = 1;

    ll cnt=0;
    FOR(i,1,L){
      ll v = s[i]-'0';
      dp1[v%2019]++; // iからはじまった分
      
      rep(j, 2019){
        ll m = (j*10+v)%2019;
        dp1[m] += dp0[j];
      }
      cnt += dp1[0];

      // reset
      rep(i,2050){
        dp0[i] = dp1[i];
        dp1[i] = 0;
      }
    }
    p(cnt);
    return 0;
}