HR 2's complement ( Digit DP )

https://www.hackerrank.com/challenges/2s-complement
It's easy to count the number of 1s that will be written in positive range with digit DP, simply remember the number of ways to reach some state will do. Let's think about cases where it's negative. With some observation, we will find that seeing 0s as 1s and vice versa, -1 is equivalent to 0, -2 to 1, x to -x - 1.

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

#define int long long

typedef long long ll;
typedef pair< int, int > pii;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< pii > vpii;
typedef vector< char > vch;

const int MOD7 = 1e9 + 7;
const int INF = 0x3f3f3f3f;

#define MULTIPLE_CASES

vi int_to_bin( int x ){
    vi res;
    stack< int > stk;
    while( x > 0 )
        stk.push( x & 1 ),
        x >>= 1;
    while( not stk.empty() )
        res.push_back( stk.top() ),
        stk.pop();
    return res;
}

ll getCount( int x, bool inc ){
    vi s = int_to_bin( x );
    vector< vector< ll > > dp( 33, vector< ll >( 2 ) );
    vector< vector< ll > > ways( 33, vector< ll >( 2 ) );
    ways[ 0 ][ 0 ] = 1;
    for( int i = 0; i < s.size(); ++i )
        for( int j = 0; j < 2; ++j )
            for( int d = 0; d < ( j ? 2 : s[ i ] + 1 ); ++d ) if( ways[ i ][ j ] )
                ways[ i + 1 ][ j || d < s[ i ] ] += ways[ i ][ j ],
                dp[ i + 1 ][ j || d < s[ i ] ] += dp[ i ][ j ] + ways[ i ][ j ] * d;
    ll res = 0;
    for( int i = 0; i < 2; ++i ){
        if( !i && !inc ) continue;
        res += dp[ s.size() ][ i ];
    }
    return res;
}

void solve(){
    int ql, qr; cin >> ql >> qr;
    ll ans = 0;
    if( qr > 0 )
        ans += getCount( qr, true );
    if( qr < -1 )
        ans -= 1LL * ( -qr - 1 ) * 32 - getCount( -qr - 2, true );
    if( ql > 0 )
        ans -= getCount( ql, false );
    if( ql < 0 )
        ans += 1LL * -ql * 32 - getCount( -ql - 1, true );
    cout << ans << "\n";
}

signed main(){
    ios::sync_with_stdio( false );
    // cin.tie( 0 ); cout.tie( 0 );

    #ifdef MULTIPLE_CASES
        int T; cin >> T; while( T-- ) solve();
    #endif

    #ifndef MULTIPLE_CASES
        solve();
    #endif

    return 0;
}