odd-even number

  1 #include<iostream>  2 #include<cstdio>  3 #include<algorithm>  4 #include<queue>  5 #include<set>  6 #include<vector>  7 #include<map>  8 #include<cstring>  9 #include<string> 10 #include<cmath> 11 using namespace std; 12 #define MS1(a) memset(a, -1, sizeof(a)) 13 #define MS0(a) memset(a, 0,sizeof(a)) 14 #define rep1(i,a,b) for(int i = a; i <= b; i++) 15 #define rep0(i,a,b) for(int i = a; i < b; i++) 16 #define rep_0(i,a,b) for(int i = b; i > a; i--) 17 #define rep_1(i,a,b) for(int i = b; i >= a; i--) 18 #define inf 0x3f3f3f3f 19 #define INF 0x3f3f3f3f3f3f3f3f 20 #define bit(p) (1<<p) 21 #define bitnum(a) __builtin_popcount(a) 22 #define lowbit(x) (x&(-x)) 23 #define eps 1e-8 24 #define mod 1000000007 25 typedef pair<int,int> PII; 26 #define ll long long 27 #define ull unsigned long long 28 #define uint unsigned int 29 #define lson l, m, rt << 1 30 #define rson m+1, r, rt << 1|1 31 #define MK make_pair 32 #define A first 33 #define B second 34 #define pb(a) push_back(a) 35 #define zero(x) (((x)>0?(x):-(x))<eps) 36 template<typename T> 37 void read1(T &m) 38 { 39     T x = 0,f = 1;char ch = getchar(); 40     while(ch <‘0‘ || ch >‘9‘){ if(ch == ‘-‘) f = -1;ch=getchar(); } 41     while(ch >= ‘0‘ && ch <= ‘9‘){ x = x*10 + ch - ‘0‘;ch = getchar(); } 42     m = x*f; 43 } 44 template<class T1, class T2> 45 void read2(T1 &a,T2 &b){read1(a);read1(b);} 46 template<class T1, class T2, class T3> 47 void read3(T1 &a,T2 &b,T3 &c){read1(a);read1(b);read1(c);} 48  49 template<class T1, class T2> 50 inline void gmax(T1& a, T2 b){ if(a < b) a = b; } 51 template<class T1, class T2> 52 inline void gmin(T1&a , T2& b){ if(a > b) a = b; } 53  54 void debug(ll bug) { cout<<"**** "<<bug<<endl;} 55 void bug(){ puts(" **** bug"); } 56 void ok(){ puts(" **** ok"); } 57 int bit[20]; 58 ll dp[20][2][20][2]; 59 ll dfs(int pos, int odd_even, int len, int zero, int on) 60 { 61     if(pos == 0) return odd_even^(len&1); 62     ll ans = dp[pos][odd_even][len][zero]; 63     if(!on && ans != -1) return ans; 64     int e = on?bit[pos]:9; 65     ans = 0; 66     for(int i = 0; i <= e; i++){ 67         if(zero == 1){ 68             if(i == 0) ans += dfs(pos-1, 0, 0, 1, 0); 69             else ans += dfs(pos-1, i&1, 1, 0, on && i == e); 70             //cout<<i<<" "<<ans<<endl; 71         } else { 72             if(i & 1){ 73                 if(odd_even & 1) ans += dfs(pos-1, odd_even, len+1, 0, on && i == e); 74                 else if(len & 1) ans += dfs(pos-1, odd_even^1, 1, 0, on && i == e); 75             } else { 76                 if(odd_even % 2 == 0) ans += dfs(pos-1, odd_even, len+1, 0, on && i == e); 77                 else if(len % 2 == 0) ans += dfs(pos-1, odd_even^1, 1, 0, on && i == e); 78             } 79         } 80     } 81     if(!on) dp[pos][odd_even][len][zero] = ans; 82     return ans; 83 } 84 ll calc(ll x) 85 { 86     int top = 0; 87     while(x){ 88         bit[++top] = x%10; 89         x /= 10; 90     } 91     return dfs(top, 0, 0, 1, 1); 92 } 93 int main() 94 { 95     MS1(dp); 96     int T, kase = 1; 97     cin >> T; 98     while(T--){ 99         ll L, R;100         read2(L,R);101         printf("Case #%d: %lld\n",kase++,calc(R) - calc(L-1));102     }103     return 0;104 }