题解：CF628D Magic Numbers

题目

• Codeforces
• Luogu

---

思路

首先可以看出这是一道数位dp。它的参数分为两个部分：是否magic和是否是 $m$ 的倍数。这两个部分其实都比较好处理：前者在dfs是判断即可（这里并不复杂，其实直接从高位开始推就行了，不用考虑奇偶位不一样问题…），后者记录一下当前$\mod m$ 的余数，最后再判断。最后，因为字符串不好减一（其实也可以减），所以需要特判一下左端点字符串。

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=2005,mod=1e9+7;

ll m,d;
string a,b;
ll dig[N];
ll len;

ll dp[N][N];

ll dfs(ll x,ll r,bool lim)
{
	if(x==len)
	{
		return r==0;
	}
	
	if(~dp[x][r]&&!lim)
	{
		return dp[x][r];
	}
	
	ll ret=0,up=lim?dig[x]:9;
	for(ll i=0;i<=up;i++)
	{
//		if(x==0&&i==0)
//		{
//			continue;
//		}
		if(x%2==0&&i!=d) //odd
		{
			ret=(ret+dfs(x+1,(r*10+i)%m,lim&&(i==up)))%mod;
		}
		if(x%2==1&&i==d) //even
		{
			ret=(ret+dfs(x+1,(r*10+i)%m,lim&&(i==up)))%mod;
		}
	}
	
	if(!lim)
	{
		dp[x][r]=ret;
	}
	return ret;
}

ll solve(string x)
{
	len=x.size();
	for(ll i=0;i<len;i++)
	{
		dig[i]=x[i]-'0';
	}
	return dfs(0,0,1);
}

bool check(string x)
{
	ll r=0; 
	for(ll i=0;i<len;i++)
	{
		if(i%2==0&&x[i]==d+'0')
		{
			return 0;
		}
		if(i%2==1&&x[i]!=d+'0')
		{
			return 0;
		} 
		r=(r*10+x[i]-'0')%m;
	}
	return r==0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	memset(dp,-1,sizeof dp);
	cin>>m>>d;
	cin>>a>>b;
	
	cout<<(solve(b)-solve(a)+check(a)+mod)%mod<<'\n';	
	
	return 0;
}