【题解】[牛客OI周赛2-提高组]C.好朋友 数位DP
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename tp>inline void read(tp&x)
{
x=0;int f=0;char ch=getchar();
while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
typedef long long ll;
ll l,r,ans,f[20][4],d[20];
int t,a[20],x,i,m;
inline ll work(ll n)
{
if(n<1000)return 0;//1000以下没有符合条件的
for(m=0;n;n/=10)a[m++]=n%10;
reverse(a,a+m);memset(f,0,sizeof(f));
f[1][0]=a[0]-1;x=0;
for(i=1;i<m;i++)
{
f[i+1][0]=f[i][0]*9;
f[i+1][1]=f[i][0]+f[i][1]*9;
f[i+1][2]=f[i][1]+f[i][2]*9;
f[i+1][3]=f[i][2]+f[i][3]*10;
f[i+1][x]+=a[i]-1;
f[i+1][x+(x<2&&a[i]||x==2&&a[i]>7)]++;
if(x<2&&!a[i]||x==2&&a[i]==7)x++;
}
return d[m-1]+f[m][3];
}
int main()
{
//freopen("in.txt","r",stdin);
for(i=0,l=1;i<=18;i++,l*=10)d[i]=work(l-1);
read(t);
while(t--)
{
read(l);read(r);ans^=work(r+1)-work(l);
}
printf("%lld\n",ans);
return 0;
}
总结
数位DP好题