题意:求某一区间内的平衡数个数(指一个数,其中出现过的数,如果是偶数,那么必须出现奇数次,反之偶数次)
题解:用三进制来枚举(0到9)所有情况,0代表没有出现,1代表出现奇数次,2代表出现偶数次dp【i】【j】i代表位数,j代表状态,在记忆化搜索的时候要记录0是否出现过
(因为之前很少写3进制的状态,写的大多数是2进制的,所以很不熟练,还是要多练,刚开始是把题意理解错了,以为是所有的奇数出现偶数次 这样,所以搞了半天也不对)
#include<bits/stdc++.h>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f; int digit[N];
ll dp[N][maxn];
bool check(int s)
{
int num[];
for(int i=;i<;i++)
{
num[i]=s%;
s/=;
}
for(int i=;i<;i++)
{
if(num[i]!=)
{
if(i%==&&num[i]==)return ;
if(i%==&&num[i]==)return ;
}
}
return ;
}
int getnews(int x,int s)
{
int num[];
for(int i=;i<;i++)
{
num[i]=s%;
s/=;
}
if(num[x]==)num[x]=;
else num[x]=-num[x];
int ans=;
for(int i=;i>=;i--)
{
ans*=;
ans+=num[i];
}
return ans;
}
ll dfs(int len,int s,bool ok,bool fp)
{
if(!len)
{
if(check(s))return ;
return ;
}
if(!fp&&dp[len][s]!=-)return dp[len][s];
ll ans=,fpmax=fp ? digit[len] : ;
for(int i=;i<=fpmax;i++)
{
ans+=dfs(len-,(ok&&i==)?:getnews(i,s),ok&&i==,fp&&i==fpmax);
}
if(!fp)dp[len][s]=ans;
return ans;
}
ll solve(ll x)
{
int len=;
while(x)
{
digit[++len]=x%;
x/=;
}
return dfs(len,,,);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int t;
cin>>t;
memset(dp,-,sizeof dp);
while(t--)
{
ll l,r;
cin>>l>>r;
cout<<solve(r)-solve(l-)<<endl;
}
return ;
}
/******************** ********************/