定义DP[pos][pre][odd][even]，pos代表当前数位，pre代表前一位的数值，odd代表到前一位连续的奇数个数，even代表到前一位连续偶数个数。
odd和even肯定至少有一个为0，而且最后的判断只和odd与even的奇偶性有关，能看出这个状态是可以被缩小到很小的，但是DP菜鸟我为了避免出错，还是定义了8万的可以接受的数组。
代码及注释如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
LL dp[][][][];
int bit[];
LL dfs(int pos,int pre,bool limit,bool lead0,int odd,int even)
{
if(pos == -)
{
if(odd== && even%==) return ;
if(even== && odd%==) return ;
return ;
}
if(!limit && !lead0 && dp[pos][pre][odd][even]!=-)///为了
///保证没有任何的歧义，前两个判定条件是必要的
{
return dp[pos][pre][odd][even];
}
int up = limit? bit[pos]: ;
LL ans = ;
for(int i = ; i <= up; i++)
{
bool Nlimit = (limit && i==up);
bool Nlead0 = (lead0 && i==);
if(lead0)///前导0存在的时候，建议特殊判断
{
if(i==) ans += dfs(pos-,i,Nlimit,Nlead0,,);
else if(i%==) ans += dfs(pos-,i,Nlimit,Nlead0,,);
else ans += dfs(pos-,i,Nlimit,Nlead0,,);
}
else
{
if( (odd%==&&i%==) || (even!=&&even%==&&i%==) ) continue;
///这两种状态是不符合要求的状态，第二个判断需要注意even = 0的情况
if(i%==) ans += dfs(pos-,i,Nlimit,Nlead0,,even+);
else ans += dfs(pos-,i,Nlimit,Nlead0,odd+,);
}
}
if(!limit && !lead0) dp[pos][pre][odd][even] = ans;
return ans;
}
LL solve(LL x)
{
int pos = ;
while(x)
{
bit[pos++] = x%;
x /= ;
}
return dfs(pos-,-,true,true,,);
}
int main()
{
// freopen("1.in.cpp","r",stdin);
int t,ca=;
LL l,r;
cin>>t;
memset(dp,-,sizeof(dp));
while(t--)
{
cin>>l>>r;
printf("Case #%d: ",++ca);
cout<<solve(r)-solve(l-)<<endl;
}
return ;
}