标题 数位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');
}