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; }