思路:
官方的题解:
没想过加下界,加上下界确实很简单。
枚举的上下界,状态为:
写出状态后发现复杂度其实很低的,只要确保状态没问题就行了。
MyCode:
#include <bits/stdc++.h> using namespace std; typedef long long int ll; inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; } ll dp[20][2][2][2][2][2][2]; bool num1[20],num2[20]; ll dfs(int len,bool limit1,bool limit2,bool limit3,bool rimit1,bool rimit2,bool rimit3) { if(len==-1) return 1; if(~dp[len][limit1][limit2][limit3][rimit1][rimit2][rimit3]) return dp[len][limit1][limit2][limit3][rimit1][rimit2][rimit3]; int ln1=limit1?num1[len]:0; int ln2=limit2?num1[len]:0; int ln3=limit3?num1[len]:0; int rn1=rimit1?num2[len]:1; int rn2=rimit2?num2[len]:1; int rn3=rimit3?num2[len]:1; ll ans=0; for(int i=ln1; i<=rn1; ++i) for(int j=ln2; j<=rn2; ++j) for(int k=ln3; k<=rn3; ++k) { if((i^j^k)==(i|j|k)) ans+=dfs(len-1,limit1&&i==ln1,limit2&&j==ln2,limit3&&k==ln3,rimit1&&i==rn1,rimit2&&j==rn2,rimit3&&k==rn3); } return dp[len][limit1][limit2][limit3][rimit1][rimit2][rimit3]=ans; } int main() { int L=read(),R=read(); memset(dp,-1,sizeof dp); for(int i=0,tmp=1; i<20; ++i) { num1[i]=L&tmp; num2[i]=R&tmp; tmp<<=1; } printf("%lld\n",dfs(19,true,true,true,true,true,true)); }