b题

没什么想法,一看题,这不裸的数位dp板子么,一敲代码,板子是什么东西来着?

考虑dp[i][0]为状态第i位数字之后,偶数的个数
dp[i][1]为状态第i位数字之后,奇数的个数
从高位向低位搜索,若当前有奇数个1,那么返回偶数个数,否则返回奇数个数
剩下的就是板子的活了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,cnt;
ll l,r;
ll digit[100];
ll dp[100][2];
ll path[100];
void split(ll x){
    cnt = 0LL;
    while(x){
        digit[++cnt] = x&1;
        x >>= 1;
    }
}
/// 12345
/// 54321
ll dfs(ll len,ll odd,ll limit){
    if(!len)return odd;
    if(!limit && ~dp[len][odd^1])return dp[len][odd^1];
    ll Max = limit?digit[len]:1LL;
    ll sum = 0LL;
    for(ll i=0LL;i<=Max;i++){
        //path[len] = i;
        sum += dfs(len-1,odd^i,limit && i == Max);
    }
    return limit?sum:dp[len][odd] = sum;
}
ll solve(ll n){
    if(!n)return 0LL;
    split(n);
    memset(dp,-1,sizeof dp);
    return dfs(cnt,0LL,1LL);
}
int main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",solve(r)-solve(l-1));
    }
    return 0;
}