上次好像接触过一次数位DP……因为有数学在里面，所以转移起来比较麻烦 数位的DP用于数字中的统计，尤其是和模有关系的 这题DP[I][J][K]表示前i个，模m为j，是否达到上限，然后转移……要考虑不少转移时候的细节 要求区间a到b，你只要求0到a和0到b就可以了，然后相减，数位dp主要是因为题目要求的是倍数关系，或者模，所以只要保存前i位的模就可以进行状态转移 感觉还是没把细节考虑清楚 DP初始化的时候也要考虑清楚…… 代码有过了一般的测试点，有几个没过。。不管 //感觉还是要想清楚之后再编程，不然bug太多了 #include #include #include #include using namespace std; typedef long long LL; int a[2005]; int b[2005]; int m,d; LL dp[2001][2001][2];//前i位，模m等于j的种数，如果和b前i位相等，就取1 const int M = 1000000007; int n = 0; LL solve(int *b) { memset(dp,0,sizeof(dp)); dp[0][0][1] = 1; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) for(int k = 0; k < 2; k++) if (i % 2 == 0){//填充奇数位 if (k == 0){//随便填，不能等于d for(int p = 0; p <= 9; p++) if (p != d) dp[i + 1][(j*10 + p) % m][0] = (dp[i + 1][(j*10 + p) % m][0] + dp[i][j][k]) %M; } else{ //填充第一位不能为0 if (b[i + 1] != d && !(i == 0 && b[i + 1] == 0))dp[i + 1][(j * 10 + b[i + 1])%m][1] = (dp[i + 1][(j * 10 + b[i + 1])%m][1] + dp[i][j][k])%M;//是第一位的时候不能填0，其他位不能填d for(int p = 0; p < b[i + 1]; p++) if (p != d && !(i == 0 && p == 0)) dp[i + 1][(j * 10 + p) %m][0] = (dp[i + 1][(j * 10 + p) %m][0] + dp[i][j][k])%M; } } else{//填充偶数位 int jj =(j * 10 + d) % m ; if(k == 0) dp[i + 1][jj][0] = (dp[i + 1][jj][0] + dp[i][j][k])%M;//填d else{ if(b[i + 1] > d) dp[i + 1][jj][0] = (dp[i + 1][jj][0] + dp[i][j][k])%M;//变成7之后就不是b的前缀了 else if (b[i + 1] == d) dp[i + 1][jj][1] = (dp[i + 1][jj][1] + dp[i][j][k])%M;//还是b的前缀 //其他情况，不能变成d } } return (dp[n][0][1] + dp[n][0][0]) % M;//和就是b和不是b } int main() { cin >> m >> d; getchar(); char c; while((c = getchar()) != ' ') a[++n] = c -'0'; n = 0; while((c = getchar()) != ' ') b[++n] = c -'0'; //cout << solve(b); //cout << solve(a); cout << (solve(b) - solve(a) + M) %M; }