CodeForces 628D(数位DP)
题意：
d-数：数字d有且只在偶数位上，奇数位不能出现数字d。(0<=d<=9)，然后给定一个区间[L, R]，问区间里面可以被m整除的d-数个数。(题意我抄网上的...)
思路：
L,R范围较大，用string模拟。
dp[i][j][k]：处理到第i位前对m取模为j且k表示忽略前导零之后i属于的位置是偶数位还是奇数位(暂时称作有效位)。
详情看代码：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 2005;
const int mod = 1e9+7;
LL ans, asa;
LL dp[maxn][maxn][2];
int m, d;
int wei[maxn];
string a, b;
string subtract(string s)
{
if(s[0] == '0' && s.length() == 1) return "-";//a = 0使用'-'标记
--s[s.length()-1];
for(int i = s.length()-1; i > 0; --i)
{
if(s[i] < '0') s[i] += 10, s[i-1] -= 1;
}
while(s.length() && s[0] == '0') s.erase(s.begin());
if(!s.length()) return "0";
return s;
}
LL dfs(int pos, int limit, int lead, int pre, int fact)
{
if(pos == -1)
{
if(pre) return 0; //最终模数不为0，不符合
if(lead && !d) return 0; //一直都是前导零，当d不为0时满足
return 1;
}
if(!limit && !lead && dp[pos][pre][fact&1] != -1) return dp[pos][pre][fact&1];
int up = limit? wei[pos]: 9;
LL tmp = 0;
if(fact&1) //如果有效位为奇(从0开始的，奇表示的偶数位)
{
//那么此时该位必须为d
if(up >= d) tmp += dfs(pos-1, limit&&d==wei[pos], lead&&d==0, (pre*10+d)%m, fact+1);
tmp %= mod;
}
else //有效位为偶则在可取范围内取任意一个不等于d的值
{
for(int i = 0; i <= up; ++i)
{
if(lead && i == 0) //之前都为前导零则再取零则有效位仍然为0
{
tmp += dfs(pos-1, limit&&i==wei[pos], lead, 0, 0);
tmp %= mod;
}
else
{
if(i == d) continue; //取不等于d的值
tmp += dfs(pos-1, limit&&i==wei[pos], lead&&i==0, (pre*10+i)%m, fact+1);
tmp %= mod;
}
}
}
if(!limit && !lead) dp[pos][pre][fact&1] = tmp;
return tmp;
}
LL solve(string s)
{
int pos = 0;
if(s[0] == '-') return 0;
for(int i = s.length()-1; i >= 0; --i) wei[pos++] = s[i]-'0';
return dfs(pos-1, 1, 1, 0, 0);
}
int main()
{
ios::sync_with_stdio(0);
memset(dp, -1, sizeof dp);
cin >> m >> d;
cin >> a >> b;
a = subtract(a);//模拟a-1;
cout << ((solve(b)-solve(a)+mod)%mod) << endl;
//防止取模之后相减为负数
return 0;
}继续加油~