统计0的个数,再判断有没有前导0,如果出现了007就记录,然后用相应的四位数组进行记忆化,比较常规的数位dp
#include <bits/stdc++.h> using namespace std; #define int long long int a[20]; int f[20][20][2][2]; int dp(int pos,int num0,bool h007,bool have,bool flag) { if(pos==0) return h007; if(flag&&f[pos][num0][h007][have]!=-1) return f[pos][num0][h007][have]; int x=flag?9:a[pos]; int ans=0; for(int i=0;i<=x;i++) { ans += dp(pos - 1, num0 + (have && i == 0), h007||(num0>=2&&i==7), i || have,flag||i<x); } if(flag) f[pos][num0][h007][have]=ans; return ans; } int cul(int x) { int pos=0; while(x) { a[++pos]=x%10; x/=10; } return dp(pos,0,false,false,false); } signed main() { memset(f,-1,sizeof(f)); int t; scanf("%lld",&t); int ans=0; while(t--) { int l,r; scanf("%lld%lld",&l,&r); ans^=cul(r)-cul(l-1); } printf("%lld\n",ans); }