coding/digit_dp.cpp at master · chayankumar999/coding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
// Type 1

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define mem(a, x) memset(a, x, sizeof(a))

string s;  int sz;
ll dp[20][150][2];

ll call(int p, int sm, int  f)
{
    if(p==sz)         return sm;
    if(~dp[p][sm][f]) return dp[p][sm][f];
    ll ret=0;
    if(f)
    {
        for(int i=0; i<10; i++)
        {
            ret+=call(p+1, sm+i, f);
        }
    }
    else
    {
        for(int i=0; i<s[p]-'0'; i++)
        {
            ret+=call(p+1, sm+i, 1);
        }
        ret+=call(p+1, sm+s[p]-'0', 0);
    }
    return dp[p][sm][f]=ret;
}
void Tostring(ll x)
{
    s = "";
    while(x)
    {
        s+=(x%10 + '0'); x/=10;
    }
    reverse(s.begin(), s.end());
    sz = s.size();
}
int main()
{
    ll a, b, r, tc;
    cin>>tc;
    while(tc--)
    {
        cin>>a>>b;

        mem(dp, -1);
        Tostring(b);
        r = call(0, 0, 0);

        if(a-1>0)
        {
            mem(dp, -1);
            Tostring(a-1);
            r -= call(0, 0, 0);
        }
        cout<<r<<endl;
    }
    return 0;
}


//Type 2
// https://codeforces.com/contest/1245/problem/F


#include<bits/stdc++.h>
using namespace std;
#define FasterIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef long long ll;
#define mem(a,x) memset(a,x,sizeof(a))

bitset<32>L, R;
ll dp[32][2][2][2][2];

/*
Problem: number of pair L<=a<=R, L<=b<=R so that aXORb = a+b
here xor of L1 and R1 = L1+R1;
sm1 and s1 check that if L1 is less than R.
sm2 and s2 check that if R1 is less than R.
lg1 and l1 check that if L1 is greater than L.
lg2 and l2 check that if R1 is greater than L.

*/
ll call(int p, int sm1, int sm2, int lg1, int lg2)
{
    if(p<0) return 1;

    if(~dp[p][sm1][sm2][lg1][lg2]) return dp[p][sm1][sm2][lg1][lg2];

    ll ret=0;
    for(int i=0; i<2; i++)
    {
        if(lg1==false && i<L[p]) continue;
        if(sm1==false && i>R[p]) continue;
        for(int j=0; j<2; j++)
        {
            if(lg2==false && j<L[p]) continue;
            if(sm2==false && j>R[p]) continue;
            if(i&j)                  continue;
            bool s1=sm1|(i<R[p]);
            bool s2=sm2|(j<R[p]);
            bool l1=lg1|(i>L[p]);
            bool l2=lg2|(j>L[p]);
            ret+=call(p-1, s1, s2, l1, l2);
        }
    }
    return dp[p][sm1][sm2][lg1][lg2]=ret;
}
int main()
{
    FasterIO;

    int tc;
    cin>>tc;
    while(tc--)
    {
        mem(dp, -1);
        int l, r;
        cin>>l>>r;
        L=bitset<32>(l);
        R=bitset<32>(r);
        cout<<call(31, 0, 0, 0, 0)<<endl;
    }
    return 0;
}