裏紙

ほぼ競プロ、たまに日記

CF 628 D - Magic Numbers

問題

Problem - D - Codeforces

問題概要

10進表記の数字を考えて、上から数えて偶数桁目の数が全てdで、奇数桁目の数がdではないものをd-magicであるという。a以上b以下の数字のうち、mの倍数かつd-magicであるものの個数を10^9+7で割った余りを求めよ。ただし、aとbは桁数が同じで、桁数は2000を超えない。

イデア

桁数が大きいので、mの倍数ってところをどうすればいいんだ...と悩み続けて終わってしまった。巨大な数の剰余は以前にもABCでやっており、すっかり頭の中から消え去ってしまっていた...上の桁から順に見ていって、逐次(10*a+b)%mで更新していけば良い。あとは再帰によって実現できる。最終的に剰余が0になっていればその数は題意を満たしていることになる。

また、区間[a,b]が決まっているので今注目している桁の数字を決定する際に、すでにaより大きいことが確定しているか、bより小さいことが確定しているかどうかの情報が必要になる。まだaより大きいことが確定していなければ今注目している桁においてaより小さい値をその桁の値として選ぶことは出来ないからである。bに関しても同様。

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(i=0;i<n;++i)
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define mp make_pair
#define pb push_back
#define fi first
#define sc second

const long mod=(long)1e9+7;

long m,d;
string a,b;

//現在注目している位置、mでの剰余、最小値より大きいことが確定しているか、最大値より小さいことが確定しているか
long dp[2001][2001][2][2];

long rec(long now, long r, int small, int large){

  if(dp[now][r][small][large]>=0)
    return dp[now][r][small][large];

  long ret=0;
  if(now==a.size()) ret=(r==0);
  else{
    for(int i=0; i<=9; ++i){
      //d以外を選ぶ
      if(now%2==0 && i==d) continue;
      //dしかダメ
      if(now%2==1 && i!=d) continue;

      //まだaより大きいことが確定していないのにaより小さい値を選ぶのはダメ
      if(small==0 && i<a[now]-'0') continue;
      //まだbより小さいことが確定していないのにbより大きい値を選ぶのはダメ
      if(large==0 && b[now]-'0'<i) continue;

      ret+=rec(now+1, (r*10+i)%m, small||a[now]-'0'<i, large||i<b[now]-'0');
      ret%=mod;
    }
  }

  return dp[now][r][small][large]=ret;
}

int main(int argc, char const *argv[]) {
  cin >>m >>d;
  cin >>a >>b;

  memset(dp,-1,sizeof(dp));
  std::cout << rec(0,0,0,0) << std::endl;
  return 0;
}