数位 DP 题，较为套路。
定义状态 \(\mathrm{dp[pos][res]}\) 表示当前填到第 \(\mathrm{pos}\) 位，模 \(m\) 余数为 \(\mathrm{res}\)，满足题意的数的个数。当 \(\mathrm{pos=0}\) 且 \(\mathrm{res=0}\) 时，计入总数。
由于记忆化搜索时是从高位往低位填，但对应的下标为 \(\mathrm{len}\) 到 \(1\)，所以第 \(\mathrm{pos}\) 位从题目角度看应为第 len-pos+1 位。
Q ：\([l,r]\) 范围内的数字并不能存在前导零，否则奇偶位数无法判断。故需要判断前导零，这样状态中就应该再加一维，变成 \(\mathrm{dp[pos][len][res]}\)，才能防止状态的重复。但这样空间就到达了 \(\mathrm{O(2000^3)}\)，必定会 MLE。
A ：确实如此。但是题目中提到了：保证 \(l,r\) 位数相同。因此如果我们不管前导零，那么那些不合法的状态的数，去除前导零后的位数一定是比 \(l,r\) 的位数都要小的，而这些数在统计 \(l\) 和 \(r\) 的时候都会被计算，相减后就会被抵消，因此不合法的状态都会被剔除，无需考虑前导零。
根据题目奇偶位限制，对应写出一下代码：
for(int i=0;i<=up;i++)
{
int wei=(len-pos+1);
ll tmp=0;
if(wei&1)
{
if(i!=d)tmp=dfs(pos-1,len,(res*10+i)%m,limit&&i==up);
}
else
{
if(i==d)tmp=dfs(pos-1,len,(res*10+i)%m,limit&&i==up);
}
ans=(ans+tmp)%mod;
}
注意到数据范围：\(1\le l\le r\le10^{2000}\)。因此 \(l\) 和 \(r\) 是以字符串形式读入的。普通的 solve(r)-solve(l-1) 因为 l-1 的难以实现而行不通。
因此我们需要单独判断 \(l\) 是否满足条件，直接模拟即可。注意位数与读入时下标间的不同。
ll solve_for_l()
{
int len=strlen(l),res=0;
for(int i=0;i<len;i++)
{
int ss=(l[i]^48);
if((i+1)&1)
{
if(ss==d)return 0;
}
else
{
if(ss!=d)return 0;
}
res=(res*10+ss)%m;
}
return res==0;
}
因此答案即为 solve(r)-solve(l)+solve_for_l()，注意取模细节。