标题数位DP

zzq和他的位运算

首先将区间 [L , R] 看成 [1,L-1] 和 [1, R] ,即结果 res = dp( R ) - dp( L-1 ) ;
对于区间【 1 ， N 】：
对于 N : N 的二进制（ xxxx xxxx ），对于第X位，如果该位为 1 ，则对于剩余的位数只需要求组合数即可,否则跳过；先预处理组合数，利用公式： f[i][j] = f[i-1][j] + f[i-1][j-1] ;

//cnt 表示当前1的个数
//M 表示当前剩余未确定的二进制位数
for( int i = (！(cnt&1) ); i <= M ; i += 2 ) //因为只求奇数，故每次加二

正式代码：

//cin.tie(0),cout.tie(0);  进一步加快执行效率.    不能和scanf与printf连用.
//cout << fixed << setprecision() << ;
//floor();向下取整
//ceil();向上取整
//rand();随机数
#include <bits/stdc++.h>
// #include <iostream>
// #include <cstring>
// #include <algorithm>
using namespace std;
//typedef long long ll; //  -9223372036854775807ll - 1 ~ 9223372036854775807ll 9e+18
//typedef unsigned long long ull;
//typedef unsigned int uint;
#define int long long
#define INF 0X7FFFFFFF
#define MAXN 1000005
#define nullptr 0
#define debug(x) cout<<#x<<" : "<<x<<endl
#define Enter(i,n) (i==n) ? cout<<endl : cout<<" "
#define loop(i,x,n) for( int i = x ; i <= n ; ++i )
#define loop_(i,x,n) for( int i = x ; i >= n ; --i )
#define input(x) scanf("%lld",&x)
#define output(x) printf("%lld",x)
#define new_line printf("\n")
#define blank printf(" ")
const int MAX=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int Max=998244353;
const double eps=1e-8;
void solve();
int GCD(int a,int b);
inline int read();
inline void write(__int128_t x);
int min(int x,int y){if(x<=y)return x;return y;}
int max(int x,int y){if(x>=y)return x;return y;}
//int Go[4][2]={ {1,0},{0,1},{-1,0},{0,-1} };

int QuickPow( int x , int pow )
{
    int res = 1 ;
//    x %= Max ;
//    pow %= Max ;
    while( pow ){
        if( pow & 1 ) res = ( res * x ) ;
        x = ( x * x ) ;
        pow >>= 1 ;
    }
    return res ;
}

bool Is_prime(int x)
{
    if( x == 0 || x == 1 ) return false ;
    if( x == 2) return true ;
    for( int i = 2 ; i*i <= x ; i++ ){
        if( x%i == 0 ) return false ;
    }
    return true ;
}

// ------------------------------------------------------------


const int N = 64 ;

int f[N][N] ;
void init()
{
    loop( i , 0 , N-1 ) f[i][0] = 1 , f[i][i] = 1 ;
    loop( i , 1 , N-1 ){
        loop( j , 1 , i ){
            f[i][j] = f[i-1][j] + f[i-1][j-1] ;
        }
    }
    return ;
}
vector< int > num ;

int dp( int n )
{
    num.clear() ;
    if(!n) return 0 ;
    while( n ) num.push_back( n%2 ) , n >>= 1 ;
    int cnt = 0 ;
    int res = 0 ;
    loop_( i , (int)num.size()-1 , 0 ){
        int x = num[i] ;
        // cout << x << endl ;
        if( x ){
                for( int j = ( ! (cnt&1) ) ; j <= i ; j += 2 ){
                    res += f[i][j] ;
                }
            cnt++ ;
        }
        if( !i && cnt&1 ) res++ ;
    }
    return res ;
}
void solve()
{
    init() ;
    int Q ;
    cin >> Q  ;
    int l , r ;
    while( Q -- ){
        cin >> l >> r ;
        cout << dp(r) - dp(l-1) << endl ;
        // int res = 0 ;
        // loop( i , l , r ){
        //     int cnt = 0 ;
        //     int x = i ;
        //     while( x ){
        //         cnt++ ;
        //         x &= (x-1) ;
        //     }
        //     if( cnt&1 ) res++ ;
        // }
        // cout << res << endl ;
    }
    return ; 
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
//    clock_t start,last;
//    start = clock();
    int _ = 1 ;
    // input( _ ) ;
    // cin >> _ ;
    while( _-- ){
//        srand( (int)time(0) ) ;
        solve() ;
    }
//    system("pause");
//    last = clock();
//    cout<<(double)(last-start)/CLOCKS_PER_SEC;
//    printf("%lf\n",(double)(last-start)/CLOCKS_PER_SEC ) ;
    return 0;
}


int GCD(int a,int b)
{
    if(b)return GCD(b,a%b);
    return a;
}

inline int read()
{
    int x = 0, t = 1;
    char ch=getchar(); // 读入单个字符到寄存器
    while(ch<'0'||ch>'9'){
        if(ch=='-')t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);  // 移位与异或
            // 第十行可以换成 x = x * 10 + ch - '0'
        ch=getchar();
    }
    return x*t;
}

inline void write(__int128_t x)
{
    if(x<0){
   	putchar('-');
		x=-x;
	}
    if(x>9) write(x/10);
     putchar(x%10+'0');
}

题解 | #zzq和他的位运算#

标题 数位DP

标题数位DP