a(i,j)保存的是以数字j开头，长度为i的数中（包含前导0）不包含P的数的数量。
函数cal的主体部分DP完成数组a的计算。
count的主体部分利用数组a完成数值n以内（包含n）不包含p的数的数量统计。返回时用n + 1(包含0）减去不包含p的数量，即是包含p的数量。

cal函数返回R以内包含p的数量减去L以下包含p的数量，即是这个区间内数值包含p的数量。

算法的思路不会有错，我有些怀疑是不是你们的题目描述出错了，主要是测试样例的实际范围是不是比题目描述的大？

正在做验算。验算n以内包含p的数量统计是否有误。通过对全部100亿组数据做上面算法与可靠的枚举结果的完全对比来验证算法的正确性。

这个过程大约耗时两个半小时，目前已经完成约33%。

[ 本帖最后由 beyondyf 于 2014-1-27 12:01 编辑 ]

这是验算用的代码。

#include<stdio.h>
#include<time.h>

int count(int a[][10], int p0, int p1, int n)
{
    int b[8], bn, c = 0, i, m;
    if(n <= 0) return 0;
    for(m = n, bn = 0; m; m /= 10) b[bn++] = m % 10;
    for(m = --bn; m >= 0; m--)
    {
        for(i = 0; i < b[m]; i++)
            if(i != p0 || p1 && (m == bn || b[m + 1] != p1)) c += a[m][i];
        if(b[m] == p0 && (!p1 || m < bn && b[m + 1] == p1)) break;
    }
    if(
        m < 0 &&
        (bn || p1 || b[0] != p0) &&
        (!bn || b[0] != p0 || p1 && b[1] != p1)
    ) c++; 
    return n - c + 1;
}

int cal(int n, int p)
{
    int a[8][10], p0, p1, c, i, j;

    p0 = p % 10;
    p1 = p / 10;
    for(c = j = 0; j <= 9; j++) c += a[0][j] = p != j;

    for(i = 1; i < 8; i++)
    for(a[i][0] = c, c = 0, j = 0; j <= 9; c += a[i][j++])
        a[i][j] = (j==p) ? 0 : (j==p1) ? a[i][0] - a[i-1][p0] : a[i][0];

    return count(a, p0, p1, n);
}

int cal2(int n, int p)
{
    int e, t;
    for(e = 1, t = p; t; t /= 10) e *= 10;
    for(; n >= p; n /= 10)
        if(n % e == p) return 1;
    return 0;
}

int main()
{
    int i, j, c;
    for(i = 1; i < 100; i++)
    {
        for(c = j = 0; j < 100000000; j++)
        {
            c += cal2(j, i);
            if(c != cal(j, i))
            {
                printf("cal(%d, %d) = %d, c = %d\n", j, i, cal(j, i), c);
                break;
            }
            if(!(j & 0xffffff)) printf("[%2d] %d (%d ms)\n", i, j, clock());
        }
        if(j < 100000000) break;
    }
    printf("use %d ms\n", clock());
    return 0;
}

验算完成，在验算的范围内无误。于是重新阅读了一遍题目，发现我看错了一个条件，L、R的范围是小于等于10^8。之前我理解成了小于10^8。

将我代码中所有的“8”都改成“9”就OK了。实际去楼主学校的OJ提交了一下，15ms AC。

因为修改的地方很少，算法本身没有错误，就不修改或重发代码了。