題意：
在范圍內滿足所給的運算符的數有多少個。
“/” 代表前面的比後面的小 “-”代表前面和後面一樣 “\” 代表前面的比後面的大
測試過會出現重復的符號 比如 "///\"
思路：
細心啊細心啊。。！！
數位dp，按位dp
注意幾個點就好了：
1、n個運算符至少要有n+1個數。
2、注意開始的狀態，第一個數以及第一個運算符。
3、運算符後移注意移動到結束標識就直接返回0。
4、運算符能往後移就往後移。
5、注意大數減一的計算。
6、注意減法的取模。
代碼：
#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
using namespace std;
//2014年9月26日12:49:21
__int64 dp[102][102][12];
int num[102],m=100000000; //因為8位數 所以對100000000取模
char v[102];
int ok(int n,int y,int z)
{
if(n>=101) //特判101
{
if(n==101) n=0;
else return 0;
}
if(v[n]=='\0') return 0; //注意如果字符串結束了 返回0
char x=v[n];
if(x=='/') return yz;
}
__int64 dfs(int site,int n,int cur,int zero,int f) //位數，運算符，前一個數，前導零，是否是邊界
{
if(site==0)
{
if(zero) return 0;
int tep=strlen(v)-1; //是否取到了最後一位
return tep==n;
}
if(!f&&!zero&&~dp[site][n][cur]) return dp[site][n][cur];
int len=f?num[site]:9;
int ans=0;
for(int i=0; i<=len; i++)
{
if(zero)
{
if(i==0) ans+=dfs(site-1,n,cur,zero&&i==0,f&&i==len);
else
{
if(cur==10) ans+=dfs(site-1,101,i,zero&&i==0,f&&i==len); //首先第一位直接放進去 然後因為只有一個數還不能確定運算符
else
{
if(ok(n+1,cur,i)) ans+=dfs(site-1,n+1,i,zero&&i==0,f&&i==len); //這裡的原則是運算符能往後走就往後走
else if(ok(n,cur,i)) ans+=dfs(site-1,n==101?0:n,i,zero&&i==0,f&&i==len); //保持原樣，然後就是101代表第二個數 因為-1會越界
}
}
}
else
{
if(cur==10) ans+=dfs(site-1,101,i,zero&&i==0,f&&i==len);
else
{
if(ok(n+1,cur,i)) ans+=dfs(site-1,n+1,i,zero&&i==0,f&&i==len);
else if(ok(n,cur,i)) ans+=dfs(site-1,n==101?0:n,i,zero&&i==0,f&&i==len);
}
}
ans%=m;
}
if(!f&&!zero) dp[site][n][cur]=ans;
return ans;
}
__int64 solve(char *x,int f) //f用來區分是否要減一
{
int i=0,cnt=0;
int len=strlen(x);
while(x[i]=='0') i++; //去前導0
if(x[i]=='\0') return 0; //如果是0
for(int j=len-1; j>=i; j--) num[++cnt]=x[j]-'0'; //放入num
if(f) //減一
{
num[1]--;
for(int j=1; j<=cnt; j++)
{
if(num[j]<0)
{
num[j]+=10;
num[j+1]--;
}
}
}
if(num[cnt]==0) cnt--; //注意退位
return dfs(cnt,101,10,1,1);
}
int main()
{
while(scanf("%s",v)!=-1)
{
memset(dp,-1,sizeof(dp));
char x[123],y[123];
scanf("%s%s",x,y); //比較長 要用字符串讀入
printf("%08I64d\n",(solve(y,0)-solve(x,1)+m)%m); //減法一定注意取模。。
}
return 0;
}
//2014年9月26日19:08:24
