CF 628 D - Magic Numbers
問題
問題概要
10進表記の数字を考えて、上から数えて偶数桁目の数が全てdで、奇数桁目の数がdではないものをd-magic
であるという。a以上b以下の数字のうち、mの倍数かつd-magic
であるものの個数をで割った余りを求めよ。ただし、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; }