dh的帽子
就是个模板,但是我脑子抽了
感觉白学了数位dp,连个模板都,不会
不想解释了,代码写的很清楚
就是用3个维度维护是否大于下界,3个变量维护是否小于上界
#include <bits/stdc++.h> using namespace std; #define int long long int a[39],b[39],dp[49][2][2][2][2][2][2]; int dfs(int len,int is1,int is2,int is3,int lim1,int lim2,int lim3) { if( len==0 ) return 1; if( dp[len][is1][is2][is3][lim1][lim2][lim3]!=-1 ) return dp[len][is1][is2][is3][lim1][lim2][lim3]; int one = lim1?b[len]:1; int two = lim2?b[len]:1; int three = lim3?b[len]:1,ans=0; for(int i=is1?a[len]:0;i<=one;i++) for(int j=is2?a[len]:0;j<=two;j++) for(int q=is3?a[len]:0;q<=three;q++) { if( (i|j|q)!=(i^j^q) ) continue; ans+=dfs(len-1,is1&&(i==a[len]),is2&&(j==a[len]),is3&&(q==a[len]),lim1&&(i==b[len]),lim2&&(j==b[len]),lim3&&(q==b[len])); } dp[len][is1][is2][is3][lim1][lim2][lim3]=ans; return ans; } int solve(int l,int r) { memset(dp,-1,sizeof(dp)); while( l ){ a[++a[0]]=(l&1), l>>=1; } while( r ){ b[++b[0]]=(r&1), r>>=1; } return dfs(b[0],1,1,1,1,1,1); } signed main() { int l,r; cin >> l >> r; cout << solve(l,r); }