题目大意:
给你两个数 \(l,r\),定义 \(bal(x)\) 代表 \(x\) 是否满足出现过的每一数位,每个偶数出现奇数次,每个奇数出现偶数次。求
\[\sum \limits_{i=l}^{r} bal(i)
\]
思路:
看到记录每一数位出现几次,就是直接告诉你这是数位dp。至于如何记录每个数出现过多少次,我们可以选择状压,用一个二进制数 \(cnt\) 代表这一数位是否出现过,再用一个 \(sta\) 记录每个数出现了几次。
由于每个数位要么出现奇数次,要么出现偶数次,我们可以用 \(1\) 代表出现了奇数次,用 \(0\) 代表出现了偶数次,只要用异或对应的数位,就能代表当前的状态 \(sta\)。
而 \(cnt\) 代表是否出现过,我们可以用或运算记录每一数位是否出现。而且可以发现,奇数位无论是否出现,最终对应的二进制数的奇数位一定是 \(0\)。所以我们只要记录偶数位是否出现即可。
这样,我们只要开个 $19 \times 2^{10} \times 2^{10} $ 的数组写记搜,这题就可以轻松加愉快的 AC 了。MLE?请看看右上角的 1.46GB。
最终 AC:90ms,201MB。
代码:
可能非常压行。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define TP template<typename T>
#define TP_ template<typename T,typename ... T_>
TP void read(T &x)
{
x=0;int f=0;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())ch=='-'&&(f=1);
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
f&&(x=-x);
}
TP_ void read(T &x,T_&...y){read(x);read(y...);}
TP void write(T x){x<0&&(putchar('-'),x=-x);static int sta[35];int top=0;do{sta[++top]=x%10;x/=10;}while(x);while(top){putchar(sta[top--]^48);}}
TP void writeln(const T x){write(x);puts("");}
TP void writesp(const T x){write(x);putchar(32);}
TP_ void writeln(const T x,T_ ...y){writesp(x);writeln(y...);}
using LL=unsigned long long;
constexpr int N=25;
constexpr int B=10;
LL dp[N][1<<B][1<<B],a[N],len;
LL dfs(int pos,bool lead,int sta,bool limit,int cnt)
{
if(!pos)return sta==cnt;
if(!limit&&!lead&&~dp[pos][sta][cnt])return dp[pos][sta][cnt];
int res=0,up=limit?a[pos]:B-1;
for(int i=0;i<=up;i++)
res+=dfs(pos-1,lead&&!i,(lead&&!i)?0:(sta^(1<<i)),limit&&i==up,(lead&&!i)?0:((!(i&1))?(cnt|(1<<i)):cnt));
return limit?res:(lead?res:dp[pos][sta][cnt]=res);
}
LL calc(LL x)
{
len=0;
while(x)a[++len]=x%B,x/=B;
return dfs(len,1,0,1,0);
}
int main()
{
int T;read(T);
memset(dp,-1,sizeof(dp));
while(T--)
{
LL l,r;
read(l,r);
writeln(calc(r)-calc(l-1));
}
return 0;
}