传送门
Description
给定区间[L,R]，请统计有多少对整数A,B(L<=A,B<=R)满足A xor B的值在二进制表示下，去掉所有前导0后是回文串
Input
第一行包含一个正整数T(1<=T<=100)，表示测试数据的组数。
每组数据包含一行两个整数L,R(0<=L<=R<=10^12)，含义如题面所述。
Output
对于每组数据输出一行一个整数，即满足条件的整数对个数。
反正就是数位dp，从两端往中间跑，记录下大小关系，谁都会写。
#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std;ll n,m,T,f[51][16]; ll min(ll a,ll b){return a<b?a:b;} ll work(ll n,ll a,ll b){ll MMH=0;memset(f,0,sizeof(f));f[0][3]=1;for (ll i=1;i<=(n>>1);i++)for (ll qa=0;qa<2;qa++)for (ll qb=0;qb<2;qb++)for (ll ha=0;ha<2;ha++)for (ll hb=0;hb<2;hb++)if ((qa^qb)==(ha^hb)&&(i!=1||qa!=qb)){ll QA=(a>>n-i)&1,QB=(b>>n-i)&1;ll HA=(a>>i-1)&1,HB=(b>>i-1)&1;for (ll k=0;k<16;k++){ll K=k;if (QA<qa&&!(k&8)) continue;if (QB<qb&&!(k&4)) continue;if (QA>qa) K|=8;if (QB>qb) K|=4;if (HA>ha) K|=2;else if (HA<ha) K&=13;if (HB>hb) K|=1;else if (HB<hb) K&=14;f[i][K]+=f[i-1][k];}}if (n&1){ll i=n+1>>1;for (ll _a=0;_a<2;_a++)for (ll _b=0;_b<2;_b++)if (n!=1||_a!=_b){ll A=(a>>i-1)&1,B=(b>>i-1)&1;for (ll k=0;k<16;k++){ll K=k;if (A<_a&&!(k&8)) continue;if (B<_b&&!(k&4)) continue;if (A>_a) K|=8;if (B>_b) K|=4;f[i][K]+=f[i-1][k];}}}ll i=n+1>>1;for (ll k=0;k<16;k++)if (((k&8)||(k&2))&&((k&4)||(k&1))) MMH+=f[i][k];return MMH; } ll Mavis(ll a,ll b){if (b<0) return 0;ll i,j,k,mmh=0;for (i=40,j=0,k=0;i;i--){j<<=1;k<<=1;j|=(a>>i)&1;k|=(b>>i)&1;if (j==k) mmh+=j*work(i,(1ll<<i)-1,(1ll<<i)-1)+work(i,a&((1ll<<i)-1),b&((1ll<<i)-1));else mmh+=k*work(i,(1ll<<i)-1,(1ll<<i)-1)+work(i,(1ll<<i)-1,b&((1ll<<i)-1));}return mmh+b+1; } int main(){scanf("%lld",&T);while(T--){scanf("%lld%lld",&n,&m);printf("%lld\n",Mavis(m,m)-2*Mavis(m,n-1)+Mavis(n-1,n-1));} }
