# 闲聊技术贴，关于状态机,该如何处理(2)

www.myexceptions.net  网友分享于：2013-01-14  浏览：60次

------解决方案--------------------

------解决方案--------------------

------解决方案--------------------
ASML主要用于软件开发前的模型测试
http://research.microsoft.com/en-us/projects/asml/
------解决方案--------------------

http://blog.csdn.net/bluesen/archive/2006/05/18/744749.aspx
------解决方案--------------------

------解决方案--------------------

------解决方案--------------------

Description

A positive number M contains another number N, when N is a substring of M in decimal.
Such as 12 contains 12; 121 contains 12; 213 contains 13; but 102 doesn't contain 12.

Now given a positive N, just calculate the number of all the numbers that contain N in [a,b].

Input

There are several test cases,each contains three numbers:N,a,b( 1 ≤ N < 100,1 ≤ a < b ≤ 2^30).

Output

The number of the numbers.

Sample Input

13 13 1350

Sample Output

84

Source

htam60@joj

C/C++ code
```#include <iostream>
#include <deque>
#include <queue>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <list>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;

#define    FILL(a, v) memset(a, v, sizeof(a))
#define    FILLN(a, v, n) memset(a, v, sizeof(a[0]) * n)

#define    INPUT1(x) int x;scanf("%d", &x)
#define    INPUT2(x, y) int x, y;scanf("%d%d", &x, &y)
#define    INPUT3(x, y, z) int x, y, z;scanf("%d%d%d", &x, &y, &z)
#define    INPUTARRAY(arr, begin, end) for (int i = begin; i < end; ++i) scanf("%d", arr+i);

#define    FOR(v, begin, end) for (int v = begin; v < end; ++v)
#define    FORTO(v, begin, last) for (int v = beign; v <= last; ++v)
#define    FORDOWNTO(v, begin, last) for (int v = begin; v >= last; --v)
#define    FOREVER for (;;)

#define    TWO(i) (1<<i)

typedef long long int64;

inline int ExistSingle(int n, int x)
{
int dig[15], curr = 0, last = 0;
int t = n;
for (; n; n /= 10)
{
int d = n % 10;
if (d < x) dig[curr++] = d;
else if (d > x) dig[curr++] = d-1;
else
{
dig[curr] = d-1;
for (; last < curr; ++last) dig[last] = 8;
++curr;
}
}
int ans = 0, b = 1;
for (int i = 0; i < curr; ++i)
{
ans += dig[i] * b;
b *= 9;
}
return t - ans;
}

int solve_single(int n, int beg, int end)
{
return ExistSingle(end, n) - ExistSingle(beg-1, n);
}

inline int ExistDouble(int n, int (*dfa)[10], int (*cnt)[3])
{
if (n < 10) return 0;
int dig[15], len = 0;
for (; n; n /= 10) dig[len++] = n % 10;
--len;
int ans = 0;
int state = 0;
for (; len >= 0; --len)
{
FOR (j, 0, dig[len]) ans += cnt[len][dfa[state][j]];
state = dfa[state][dig[len]];
}
return ans + cnt[state][0];
}
int solve_double(int n, int beg, int end)
{
int first = n / 10, second = n % 10;
int dfa[3][10] = {0};
for (int i = 0; i < 10; ++i) dfa[2][i] = 2;
dfa[0][first] = 1, dfa[1][second] = 2;
if (first != second) dfa[1][first] = 1;
int cnt[13][3] = {0};
cnt[0][2] = 1;
FOR (i, 1, 12) FOR (j, 0, 3) FOR (k, 0, 10) cnt[i][j] += cnt[i-1][dfa[j][k]];
return ExistDouble(end, dfa, cnt) - ExistDouble(beg-1, dfa, cnt);
}
int main()
{
int n, i, j;
while (scanf("%d%d%d", &n, &i, &j) == 3)
{
if (n < 10) printf("%d\n", solve_single(n, i, j));
else printf("%d\n", solve_double(n, i, j));
}
return 0;
}
```