95 D Horse Races

問題

4,7をラッキーな数とする。
自然数t,kが与えられる。t個の整数の組a[i],b[i]について以下をmod 10^9+7で求めよ。

• a[i]以上,b[i]以下で、距離がk以下の二つのラッキーな数の組を一組以上含む数の数

制約条件

t,k≦1000
a[i],b[i]≦10^1000

方針

b[i]以下の求める数からa[i]-1以下の求める数を引けばよいので、
それぞれを計算してやる。

それぞれの計算はメモ化再帰による。
数字を先頭から見て行き、
現在の位置pos,最後にラッキーな数が現れた位置last,okかどうか、与えられた数よりsmallかどうか
であるような数の今までの数を、
rec(pos,last,ok,small)で表す。

smallが1のときは、a[i]やb[i]によらないので、メモ化できる。
smallじゃない時というのは、全桁がa[i]（b[i]）に一致しているときなので、1通りしかない。すなわちメモ化をしなくても間に合う。

よってsmallが1のときだけメモ化するメモ化再帰が使える。

ソースコード

const int mod=int(1e9+7);
int t,k;
int dp[1010][1010][2]; //pos, last, ok

int rec(string &d,int p,int last,bool ok,bool small){
	if(small&&dp[p][last+1][ok]>=0)return dp[p][last+1][ok];
	if(p==d.size())return ok;
	int ret=0;
	
	rep(i,10){
		int nlast=i==4||i==7?p:last;
		bool nok=ok, nsmall=small;
		if(last>=0&&nlast!=last&&nlast-last<=k)nok=1;
		if(i<d[p]-'0')nsmall=1;
		if(i==d[p]-'0'||nsmall)(ret+=rec(d,p+1,nlast,nok,nsmall))%=mod;
	}
	if(small)dp[p][last+1][ok]=ret;
	return ret;
}
void run()
{
	cin>>t>>k;
	rep(i,1010)rep(j,1010)rep(k,2)dp[i][j][k]=-1;
	rep(i,t){
		string a,b; cin>>a>>b;
		a=string(1001-a.size(),'0')+a; b=string(1001-b.size(),'0')+b;
		for(int j=1000;j>=0;j--){
			if(a[j]!='0'){
				a[j]--; break;
			}
			else a[j]='9';
		}
		ll ans=rec(b,0,-1,0,0)-rec(a,0,-1,0,0);
		if(ans<0)ans+=mod;
		cout<<ans<<endl;
	}
}