首页 > 代码库 > bzoj4918: 回文数对
bzoj4918: 回文数对
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>#define F(i,n) for(int i=0;i<n;++i)typedef long long i64;const int M=40;int T;i64 L,R;i64 f[M+5][3][3][3][3];i64 min(i64 a,i64 b){return a<b?a:b;}inline int tr(int a,int b){return a==1?b:a;}i64 cal(i64 m1,i64 m2){ if(m1<0||m2<0)return 0; i64 mn=min(m1,m2); i64 ans=0; for(int p1=M;p1>=-1;--p1){ memset(f,0,sizeof(f)); f[p1+1][(m1>>p1+1)==(mn>>p1+1)][1][(m2>>p1+1)==(mn>>p1+1)][1]=1; f[p1+1][0][1][0][1]+=mn>>(p1+1); int l,r; for(l=p1,r=0;l>=r;--l,++r){ int xb1=(m1>>l&1)-1,xb2=(m1>>r&1)-1; int yb1=(m2>>l&1)-1,yb2=(m2>>r&1)-1; F(x1,2)F(x2,3)F(y1,2)F(y2,3) for(int z=(l==p1);z<2;++z) F(t1,2)F(t2,2)if(l>r||t1==t2){ f[l][tr(x1,t1-xb1)][tr(t2-xb2,x2)][tr(y1,(t1^z)-yb1)][tr((t2^z)-yb2,y2)]+=f[l+1][x1][x2][y1][y2]; } } F(x1,2)F(x2,3)F(y1,2)F(y2,3)if(tr(x1,x2)!=2&&tr(y1,y2)!=2)ans+=f[l+1][x1][x2][y1][y2]; } return ans;}int main(){ for(scanf("%d",&T);T;--T){ scanf("%lld%lld",&L,&R); printf("%lld\n",cal(R,R)+cal(L-1,L-1)-cal(L-1,R)-cal(R,L-1)); } return 0;}
bzoj4918: 回文数对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。