题意：一个数字，它每个数位上的奇数都形成偶数长度的段，偶数位都形成奇数长度的段他就是好的。问[L , R]的好数个数。
题解：裸的数位dp, 从高到低考虑每个数位, 状态里存下到当前位为止的值的奇偶性和长度奇偶性即可.
#include <iostream>
#include <vector>
#include <string.h>
#include <stdio.h>
#include <queue>
using namespace std;
long long dp[][][];
int bit[];
long long dfs(int pos,int preTy,int prelen,bool flag) { //flag为true的话表示当前位触顶了
if(pos==-) {
if(prelen% != preTy) return ;
else return ;
}
if(!flag && dp[pos][preTy][prelen]!=-) return dp[pos][preTy][prelen];
int e = flag?bit[pos]:;
long long ans=;
for(int i=;i<=e;i++) {
if(prelen==&&i==) {
ans += dfs(pos-,,,flag&&i==e);
//ans += dfs(pos-1,i%2,preTy==0?prelen+1:1,flag&&i==e);
}
else if(i%==) {
if(preTy==&&prelen%==) continue;
ans += dfs(pos-,,preTy==?prelen+:,flag&&i==e);
}
else {
if(preTy==&&prelen%==) continue;
ans += dfs(pos-,,preTy==?prelen+:,flag&&i==e);
}
}
//printf("%d %d %d %d %d\n",pos,preTy,prelen,flag,ans);
if(!flag) return dp[pos][preTy][prelen]=ans;
return ans;
} long long solve(long long n) {
int pos=;
while(n) {
bit[pos++] = n%;
n/=;
}
memset(dp,-,sizeof(dp));
return dfs(pos-,,,true);
}
int main() {
int T;
long long l,r;
cin>>T;
int kase=;
while(T--) {
cin>>l>>r;
printf("Case #%d: ",kase++);
cout<<solve(r)-solve(l-)<<endl;
//cout<<solve(r)<<endl;
}
}