/* 题意： 给你l和r，范围9e18，求l到r闭区间有多少个数字满足，连续的奇数的个数都为偶数，连续的偶数的个数都为奇数。 例如33433符合要求，44不符合要求。不能含有前导零。 思路： 队友说是数位dp...我都反映不过来。 知道是数位dp以后，思路就显而易见了。 dp的方法是最后一位的性质，是偶数还是奇数，是连续的第偶数个还是第奇数个。所以一共只有四种状态，而题目中最多19位数字... 用了以上的方法，我们可以轻易解决有n为数字的符合要求的数字的个数。 问题是如何考虑边界条件。 所以我们可以先判断l和r有多少位。然后提前打表，中间的位数直接加到答案上来就好。 现在我们讨论跟l和r位数相同的在l到r范围内的，即大于等于l，小于等于r的个数。 假如l和r位数相同，那么我们可以用小于等于r的减去小于等于l的，然后特判l是不是。 位数不同，可以直接求和l位数相同的，大于等于l的加上和r位数相同的小于等于r的。 所以现在问题转化为，位数确定的情况下，小于等于或者大于等于某个数的符合条件数的个数有多少。 类似dfs，依次讨论前几位大于等于某位或者小于等于某位有多少个...（这个大概是数位dp的核心？） 【简单说一下，第i次统计的数目是，假如第i位大于边界值，而前i-1位等于边界值的符合要求的数字的数目，这样一直统计到i+1...】 */ #include<bits/stdc++.h> using namespace std; bool panduan(unsigned long long num) { int curr=0; int len=0; while(num) { int temp=num%10; if(curr==0) { if(temp%2) curr=1; else curr=2; len=1; } else { if(curr==1) { if(temp%2) len++; else { if(len%2) return false; len=1; curr=2; } } else { if(temp%2==0) len++; else { if(len%2==0) return false; len=1; curr=1; } } } num/=10; } if((curr==1)&&(len%2==0)) return true; if((curr==2)&&(len%2==1)) return true; return false; } int get_wei(unsigned long long t){ int rel=0; while(t>0){ rel++; t/=10; } return rel; } unsigned long long dp[20][4]; unsigned long long biao[30]; void dabiao(){ for(int i=1;i<=19;i++){ memset(dp,0,sizeof(dp)); for(int j=1;j<=i;j++){ if(j==1){ dp[j][0]+=4; dp[j][2]+=5; } dp[j][0]+=(dp[j-1][1]+dp[j-1][3])*5; dp[j][1]+=dp[j-1][0]*5; dp[j][2]+=(dp[j-1][0]+dp[j-1][3])*5; dp[j][3]+=dp[j-1][2]*5; } biao[i]=dp[i][0]+dp[i][3]; } } int fenjie[30]; unsigned long long dayudengyu(unsigned long long l){ unsigned long long rel=0; unsigned long long ll=l; int num=0; while(ll>0){ fenjie[num++]=ll%10; ll/=10; } for(int i=0;i<num/2;i++){ swap(fenjie[i],fenjie[num-i-1]); } memset(dp,0,sizeof(dp)); for(int i=0;i<num;i++){ for(int j=i;j<num;j++){ if(j==i){ if(fenjie[i]&1){ if(j==0){ dp[j][0]=dp[j][2]=(10-fenjie[i])/2; } else{ int ttt=(10-fenjie[i])/2; dp[j][0]=(dp[j-1][1]+dp[j-1][3])*ttt; dp[j][1]=dp[j-1][0]*ttt; dp[j][2]=(dp[j-1][0]+dp[j-1][3])*ttt; dp[j][3]=dp[j-1][2]*ttt; } } else{ if(j==0){ dp[j][0]=(10-fenjie[i])/2-1; dp[j][2]=(10-fenjie[i])/2; } else{ int ttt=(10-fenjie[i])/2; dp[j][0]=(dp[j-1][1]+dp[j-1][3])*(ttt-1); dp[j][1]=dp[j-1][0]*(ttt-1); dp[j][2]=(dp[j-1][0]+dp[j-1][3])*ttt; dp[j][3]=dp[j-1][2]*ttt; } } } else{ dp[j][0]=(dp[j-1][1]+dp[j-1][3])*5; dp[j][1]=dp[j-1][0]*5; dp[j][2]=(dp[j-1][0]+dp[j-1][3])*5; dp[j][3]=dp[j-1][2]*5; } } rel+=dp[num-1][0]+dp[num-1][3]; memset(dp,0,sizeof(dp)); for(int j=0;j<=i;j++){ if(j==0){ if(fenjie[j]&1)dp[j][2]=1; else dp[j][0]=1; } else{ if(fenjie[j]&1){ dp[j][2]=(dp[j-1][0]+dp[j-1][3]); dp[j][3]=dp[j-1][2]; } else{ dp[j][0]=(dp[j-1][1]+dp[j-1][3]); dp[j][1]=dp[j-1][0]; } } } } return rel+dp[num-1][0]+dp[num-1][3]; } unsigned long long xiaoyudengyu(unsigned long long l){ unsigned long long rel=0; unsigned long long ll=l; int num=0; while(ll>0){ fenjie[num++]=ll%10; ll/=10; } for(int i=0;i<num/2;i++){ swap(fenjie[i],fenjie[num-i-1]); } memset(dp,0,sizeof(dp)); for(int i=0;i<num;i++){ for(int j=i;j<num;j++){ if(j==i){ if(fenjie[i]&1){ if(j==0){ dp[j][0]=fenjie[i]/2; dp[j][2]=fenjie[i]/2; } else{ unsigned long long ttt=(fenjie[i])/2+1; unsigned long long tt=fenjie[i]/2; dp[j][0]=(dp[j-1][1]+dp[j-1][3])*ttt; dp[j][1]=dp[j-1][0]*ttt; dp[j][2]=(dp[j-1][0]+dp[j-1][3])*tt; dp[j][3]=dp[j-1][2]*tt; } } else{ if(j==0){ dp[j][0]=max(fenjie[i]/2-1,0); dp[j][2]=(fenjie[i])/2; } else{ int ttt=max(0,fenjie[i]/2); int tt=fenjie[i]/2; dp[j][0]=(dp[j-1][1]+dp[j-1][3])*(ttt); dp[j][1]=dp[j-1][0]*(ttt); dp[j][2]=(dp[j-1][0]+dp[j-1][3])*(tt); dp[j][3]=dp[j-1][2]*tt; } } } else{ dp[j][0]=(dp[j-1][1]+dp[j-1][3])*5; dp[j][1]=dp[j-1][0]*5; dp[j][2]=(dp[j-1][0]+dp[j-1][3])*5; dp[j][3]=dp[j-1][2]*5; } } rel+=dp[num-1][0]+dp[num-1][3]; //cout << rel << endl; memset(dp,0,sizeof(dp)); for(int j=0;j<=i;j++){ if(j==0){ if(fenjie[j]&1)dp[j][2]=1; else dp[j][0]=1; } else{ if(fenjie[j]&1){ dp[j][2]=(dp[j-1][0]+dp[j-1][3]); dp[j][3]=dp[j-1][2]; } else{ dp[j][0]=(dp[j-1][1]+dp[j-1][3]); dp[j][1]=dp[j-1][0]; } } } } return rel+dp[num-1][0]+dp[num-1][3]; } int main(){ int a; dabiao(); int cas=0; scanf("%d",&a); while(a--){ cas++; unsigned long long l,r,ll,rr; unsigned long long rel=0; scanf("%llu%llu",&l,&r); int st=get_wei(l); int ed=get_wei(r); for(int i=st+1;i<ed;i++){ rel+=biao[i]; } if(st==ed){ rel+=xiaoyudengyu(r); rel+=panduan(l); rel-=xiaoyudengyu(l); } else{ rel+=dayudengyu(l); rel+=xiaoyudengyu(r); } printf("Case #%d: ",cas); printf("%llu ",rel); } }