bzoj 4918: [Lydsy1706月赛]回文数对_综合

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4918

容易发现，合法的回文是根号级别的
因为你只用枚举前面一半
然后你发现，可以数位DP
先估算一下数位DP的复杂度，设为位数S
那么得到了 $\times T\times\sqrt{R}$ 的算法
发现过不去。。

仔细分析，发现这个根号没有用。。
直接数位DP就好了
记录一下 $f_{i,j,tf,tf1}$ 表示做到第 $i$ 位，结果的非 $0$ 位出现在哪里，是否顶边界的答案
然后当当前已确定的位（从非0位开始数），和后面的位组合起来就是要的回文串
也就是当前是一半，就直接算
如果都没有顶边界，那么明显，答案就是 $2^i$ ，让一个串随便填，另外一个根据回文来填即可
如果有一个顶边界，可以暴力枚举这个顶边界第一位不顶边界的，然后计算
否则，因为两个都顶边界，我们可以知道回文的前半段是什么，然后也是暴力枚举第一位变成第一个或第二个情况的是哪一位，然后计算就可以了

建议把有一个顶边界的预处理一下

做法很简单，但是实现有点难度。。

注意细节

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL N=50;
LL T;
LL a[N],b[N],tot;
LL f[N][N][2][2];
LL h[N],h1[N];
LL Pow[N];
LL g[N];//之前异或出来的答案是什么 
LL dfs (LL now,LL lst,bool tf,bool tf1)//上一个出现的位置是什么 是否出现了不贴边界的位 
{
    if (now<0) return 1;LL lalal=0;LL t=lst-now;if (now+1==t||now+2==t)//直接对称 {
    // printf("YES! %lld\n");if (tf&&tf1)    lalal=Pow[now+1];else if ((tf^tf1)==1)//有一个不用贴边界 {
    if (tf1==true) lalal=h[now];else lalal=h1[now];//lalal=h[now]+1;}else//都贴边界 {
    LL o=0;if (now+1==t){
    for (LL i=now+1;i<=lst;i++) g[++o]=(a[i]^b[i]);}else{
    for (LL i=now+2;i<=lst;i++) g[++o]=(a[i]^b[i]);}/* for (int i=1;i<=o;i++) printf("%lld",g[i]);printf("\n");*/bool ok=true;for (LL i=now;i>=0;i--)//从这一位开始尝试不贴边界 {
    LL id=(now-i+1);//对应什么//printf("YES:%lld %lld\n",i,id);if (a[i]==1&&b[i]==1)//都可以不贴边界{
    if (g[id]==0)//两人都不贴边界lalal=lalal+Pow[i];else{
    if (i==0) lalal+=2;else lalal=lalal+h[i-1]+h1[i-1];}}else if ((a[i]^b[i])==1)//有一个是1 {
    if (g[id]==0)//必须不贴边界了{
    if (a[i]==1) {
    if (i>0) lalal+=h1[i-1];}if (b[i]==1) {
    if (i>0) lalal+=h[i-1];}//lalal=lalal+Pow[now];}}if (g[id]!=(a[i]^b[i])) {
    ok=false;break;}}lalal=lalal+ok;}}else{
    if (tf==true&&tf1==true){
    if (lst==-1){
    lalal=lalal+dfs(now-1,-1,tf,tf1)*2;//00 11lalal=lalal+dfs(now-1,now,tf,tf1)*2;//10 01}else    lalal=lalal+dfs(now-1,lst,tf,tf1)*4;}else if (tf==true){
    for (LL i=0;i<=b[now];i++){
    if (lst==-1){
    lalal=lalal+dfs(now-1,-1,tf,i<b[now]);//00 11lalal=lalal+dfs(now-1,now,tf,i<b[now]);//10 01}else    lalal=lalal+dfs(now-1,lst,tf,i<b[now])*2;}}else if (tf1==true){
    for (LL i=0;i<=a[now];i++){
    if (lst==-1){
    lalal=lalal+dfs(now-1,-1,i<a[now],tf1);//00 11lalal=lalal+dfs(now-1,now,i<a[now],tf1);//10 01}else    lalal=lalal+dfs(now-1,lst,i<a[now],tf1)*2;}}else{
    for (LL i=0;i<=a[now];i++)for (LL j=0;j<=b[now];j++){
    if (lst==-1){
    if ((i^j)==0) lalal=lalal+dfs(now-1,-1,i<a[now],j<b[now]);else lalal=lalal+dfs(now-1,now,i<a[now],j<b[now]);}else    lalal=lalal+dfs(now-1,lst,i<a[now],j<b[now]);}}}if (f[now][lst+1][tf][tf1]!=0) return f[now][lst+1][tf][tf1];
/* printf("%lld %lld %d %d %lld\n",now,lst,tf,tf1,lalal);system("pause");*/f[now][lst+1][tf][tf1]=lalal;return lalal;
}
LL calc (LL L,LL R)
{
    if (L<0||R<0) return 0;
// printf("calc:%lld %lld\n",L,R);memset(f,0,sizeof(f));LL now=0,now1=0;a[0]=0;b[0]=0;while (L>0)  {
    a[now++]=(L&1);L>>=1;}while (R>0)  {
    b[now1++]=(R&1);R>>=1;}tot=max(0LL,max(now-1,now1-1));h[0]=h1[0]=1;//printf("%lld\n",tot);for (int u=0;u<=tot;u++) {
    if (u>0) h[u]=h[u-1],h1[u]=h1[u-1];if (a[u]==1) h[u]=h[u]+Pow[u];if (b[u]==1) h1[u]=h1[u]+Pow[u];}for (LL u=now;u<=tot;u++) a[u]=0;for (LL u=now1;u<=tot;u++) b[u]=0;
/* for (LL u=tot;u>=0;u--) printf("%lld",a[u]);printf("\n");for (LL u=tot;u>=0;u--) printf("%lld",b[u]);printf("\n");*/LL t=dfs(tot,-1,false,false);//printf("%lld\n",t);return t;
}
int main()
{
    Pow[0]=1;for (LL u=1;u<50;u++) Pow[u]=Pow[u-1]*2;    //calc(3,8);scanf("%lld",&T);while (T--){
    LL L,R;scanf("%lld%lld",&L,&R);printf("%lld\n",calc(R,R)-calc(L-1,R)-calc(L-1,R)+calc(L-1,L-1));}return 0;
}
?