【题意】求出现的数字，所有偶数出现奇数次，所有奇数出现偶数次的个数。
【解题方法】用一个三进制表示每个数字出现的状态，1表示出现过奇数次，0表示从未出现过，1表示出现过偶数次。dp[l][s]长度为i,s代表当前状态。接下来就是数位DP经典套路了。
【AC 代码】
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; LL dp[20][60000]; int digit[20]; bool check(int s) { int num[20]; for(int i=0; i<10; i++){ num[i]=s%3; s/=3; } for(int i=0; i<10; i++){ if(num[i]!=0){ if(i%2==0&&num[i]==2) return false; if(i%2==1&&num[i]==1) return false; } } return true; } int getnews(int x,int s) { int num[10]; for(int i=0; i<10; i++){ num[i]=s%3; s/=3; } if(num[x]==0) num[x]=1; else num[x]=3-num[x]; int news=0; for(int i=9; i>=0; i--){ news*=3; news+=num[i]; } return news; } LL dfs(int l,int s,bool zero,bool jud) { if(l==0){ if(check(s)) return 1; else return 0; } if(!jud&&dp[l][s]!=-1) return dp[l][s]; LL ans=0; int nex=jud?digit[l]:9; for(int i=0; i<=nex; i++){ ans+=dfs(l-1,(zero&&i==0)?0:getnews(i,s),i==0&&zero,jud&&i==nex); } return jud?ans:dp[l][s]=ans; } LL f(int num) { int pos=0; while(num){ digit[++pos]=num%10; num/=10; } return dfs(pos,0,true,true); } int main() { int T; LL a,b; memset(dp,-1,sizeof(dp)); scanf("%d",&T); while(T--){ scanf("%lld%lld",&a,&b); LL ans=f(b)-f(a-1); printf("%lld\n",ans); } return 0; }
