Mirror Number SPOJ - MYQ10

 1 #include<cstdio>
 2 #include<cstring>
 3 typedef long long LL;
 4 LL ans[60][60][2];
 5 LL w[60];
 6 LL T;
 7 char l[100],r[100];
 8 LL temp[60];
 9 LL dp(LL tot,LL pos,bool pre0,bool limit)
10 {
11     if(pos<1)    return 1;
12     if(!limit&&ans[tot][pos][pre0]!=-1)
13         return ans[tot][pos][pre0];
14     LL i,res=0,end=limit?w[pos]:9;
15     for(i=0;i<=end;i++)
16     {
17         if(i!=0&&i!=1&&i!=8)    continue;
18         temp[pos]=i;
19         if(i==0&&pre0)
20             res+=dp(tot-1,pos-1,1,0);
21             //res+=dp(tot,pos-1,1,0);这样会错
22         else if(pos>tot/2)//5-->5,4,3 6-->6,5,4 如果在前一半则可以随便填
23             res+=dp(tot,pos-1,0,limit&&i==w[pos]);
24         else if(temp[pos]==temp[tot-pos+1])//如果在后一半就必须和前一半一样
25             res+=dp(tot,pos-1,0,limit&&i==w[pos]);
26     }
27     if(!limit)    ans[tot][pos][pre0]=res;
28     return res;
29 }
30 LL get(char x[])
31 {
32     LL len=strlen(x);
33     for(LL i=0;i<len;i++)    w[len-i]=x[i]-'0';
34     return dp(len,len,1,1);
35 }
36 bool ok(char x[])
37 {
38     LL len=strlen(x);
39     for(LL i=0;i<len;i++)
40         if(x[i]!=x[len-i-1]||(x[i]!='0'&&x[i]!='1'&&x[i]!='8'))
41             return false;
42     return true;
43 }
44 int main()
45 {
46     LL iii;
47     memset(ans,-1,sizeof(ans));
48     scanf("%lld",&T);
49     for(iii=1;iii<=T;iii++)
50     {
51         scanf("%s%s",l,r);
52         printf("%lldn",get(r)-get(l)+ok(l));
53     }
54     return 0;
55 }

1 bool ok(char x[])
2 {
3     LL len=strlen(x);
4     for(LL i=0;i<len/2;i++)
5         if(x[i]!=x[len-i-1]||(x[i]!='0'&&x[i]!='1'&&x[i]!='8'))
6             return false;
7     return true;
8 }