3989 - 好奇的果沫
可怜的果沫在寒假的时候去考科目三，他坐在候车室，盯着屏幕上滚动的考场车序号，不一会，他发现所有的序列中，没有任何一个序列包含“4”这一位。于是好奇的果沫想知道是如何实现这一功能的，机智的你们能帮他解决这个问题么？
Input
第一行输入2个整数，t、k（0 < t < 10，0 < k < 100）表示有t组测试数据，第二行输入给定2个整数n、m（0 < n ≤ m < 100000000）。
Output
输出t行，每行一个整数，为区间 [n, m] 中不含 k 的数的个数
Examples
Input
1 4 1 100
Output
81
Solution C++
#include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <stack> #include <queue> #include <cmath> #include <string> #include <set> #include <map> #define NBIT 9 #define getten(a) (a/10) #define getge(a) (a%10) #define isten(a) (a >= 10) using namespace std ; int f[15][15], p ; int dig[15] ; void init () { memset (f, 0, sizeof(f)) ; f[0][0] = 1 ; for (int i=1; i<=NBIT; i++) for (int j=0; j<=9; j++) for (int k=0; k<=9; k++) if ((!isten(p) && j != getge(p)) || (isten(p) && !(j == getten(p) && k == getge(p)))) f[i][j] += f[i-1][k] ; } int getdig (int n) { int len = 0 ; while (n) { dig[++len] = n % 10 ; n /= 10 ; } return len ; } int getcount (int n) { n++ ; int len = getdig (n) ; int ans = 0 ; for (int i=len; i>0; i--) { for (int j=0; j<dig[i]; j++) //个位数的最后一位没统计到，所以统计的为[0, n-1]，要+1 if ((!isten(p) && j != getge(p)) || (isten(p) && !(i < len && dig[i+1] == getten(p) && j == getge(p)))) ans += f[i][j] ; if ((!isten(p) && dig[i] == getge(p)) || (isten(p) && (i < len && dig[i+1] == getten(p) && dig[i] == getge(p)))) break ; } return ans ; } int main() { int n, m, t ; scanf ("%d%d", &t, &p) ; init () ; for (int i=0; i<t; i++) { scanf ("%d%d", &n, &m) ; printf ("%d\n", getcount(m) - getcount(n-1)) ; } return 0 ; }