[暑假集训--数位dp]hdu5898 odd-even number

For a number,if the length of continuous odd digits is even and the length of continuous even digits is odd,we call it odd-even number.Now we want to know the amount of odd-even number between L,R(1<=L<=R<= 9*10^18).

Input

First line a t,then t cases.every line contains two integers L and R.

Output

Print the output for each case on one line in the format as shown below.

Sample Input

2
1 100
110 220

Sample Output

Case #1: 29
Case #2: 36

题意是要找x，x当中所有连续的奇数段长度是偶数，连续的偶数段长度是奇数，比如1357246

记一下当前这段是奇数还是偶数，这段已经有多长，有没有前导零。如果有前导零那么0可以也出现奇数次

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<deque>

 #include<set>

 #include<map>

 #include<ctime>

 #define LL long long

 #define inf 0x7ffffff

 #define pa pair<LL,LL>

 #define mkp(a,b) make_pair(a,b)

 #define pi 3.1415926535897932384626433832795028841971

 using namespace std;

 inline LL read()

 {

     LL x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int len;

 LL l,r;

 LL f[][][][];

 int d[];

 inline LL dfs(int now,int dat,int lst,int lead,int fp)

 {

     if (now==)return (lst&)^(dat&);

     if (!fp&&f[now][dat][lst][lead]!=-)return f[now][dat][lst][lead];

     LL ans=;

     int mx=fp?d[now-]:;

     for (int i=;i<=mx;i++)

     {

         if (i==)

         {

             if (lead)

             {

                 if (lead&&now-!=)ans+=dfs(now-,,,,fp&&mx==);

                 else if (lead&&now-==)ans+=dfs(now-,,,,fp&&mx==);

                 continue;

             }

         }

         if ((i&)==(dat&))ans+=dfs(now-,i,lst+,,fp&&i==mx);

         else if ((dat&)^(lst&)||lead)

         {

             ans+=dfs(now-,i,,,fp&&i==mx);

         }

     }

     if (!fp)f[now][dat][lst][lead]=ans;

     return ans;

 }

 inline LL calc(LL x)

 {

     if (x==-)return ;

     if (x==)return ;

     LL xxx=x;

     len=;

     while (xxx)

     {

         d[++len]=xxx%;

         xxx/=;

     }

     LL sum=;

     sum+=dfs(len,,len==,len!=,d[len]==);

     for (LL i=;i<=d[len];i++)

     {

         sum+=dfs(len,i,,,i==d[len]);

     }

     return sum;

 }

 int main()

 {

     LL T=read();int cnt=;

     memset(f,-,sizeof(f));

     while (T--)

     {

         l=read();

         r=read();

         if (r<l)swap(l,r);

         printf("Case #%d: %lld\n",++cnt,calc(r)-calc(l-));

     }

 }

hdu 5898