cf776G.Sherlock and the Encrypted Data

题意:对于一个16进制数x,把x的各个数位拿出来,设其为t1,t2,...,定义s(x)为2^t1|2^t2|...,如x=0x3e53,则s(x)=2^3|2^14|2^5|2^3=16424.给出q组询问l,r(l,r也是16进制数,不超过15位),求[l,r]中有多少个数x满足x^s(x)

这题题解写的是个状压数位dp,但是蒟蒻不会数位dp,自己YY了一个做法.

首先,将[l,r]的询问拆成2个前缀和,考虑到十六进制数减1并不方便,可以转化为solve(r)-solve(l),再特判一下l满不满足要求.

考虑求出[0,upper]间的答案.将二进制位从低位向高位,从0开始编号.观察x和s(x)的二进制表示,可以发现当且仅当s(x)的最高位1所在的数位上x也为1时,x^s(x)非常恶心比较多.

program cf776G;
const number=['a'..'f','0'..'9'];
      list:array[0..15]of char=('0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f');
var q,i:longint;
    l,r:string;
    num:array[char] of longint;
    ch:char;
procedure getstr(var s:string);
var ch:char;
begin
  s:='';
  read(ch);
  while not (ch in number) do read(ch);
  while ch in number do
  begin
    s:=s+ch;
    read(ch);
  end;
end;
function check(const x:string):longint;
var i:longint;
    t,this:int64;
begin
  this:=0;
  for i:=1 to length(x) do this:=this*16+num[x[i]];
  t:=0;
  for i:=1 to length(x) do t:=t or (1 shl num[x[i]]);
  exit(ord(this xor t<this));
end;
function solve2(const upper:string;id,up:longint):int64;
var upp,ans:int64;
    i,this,t:longint;
    sw:array[0..30] of longint;
    pow:array[0..20] of int64;
begin
  upp:=0;
  for i:=1 to length(upper) do upp:=upp*16+num[upper[i]];
  for i:=1 to length(upper) do sw[length(upper)-i]:=num[upper[i]];
  if(1 shl (id mod 4)>up)or(1 shl id>upp)or(up<0) then exit(0);
  t:=0;
  for this:=0 to up do if this and (1 shl (id mod 4))>0 then inc(t);
  ans:=0;
  pow[0]:=1;
  for i:=1 to length(upper) do pow[i]:=pow[i-1]*(up+1);
  for i:=length(upper)-1 downto 0 do
    if i=id div 4 then
    begin
      if upthen
      begin
        ans:=ans+t*pow[i];
        exit(ans);
      end;
      for this:=0 to sw[i]-1 do if this and (1 shl (id mod 4))>0 then
        ans:=ans+pow[i];
      if sw[i] and (1 shl (id mod 4))=0 then exit(ans);
    end else
    begin
      if upthen
      begin
        if i>id div 4 then ans:=ans+pow[i]*t else ans:=ans+pow[i+1];
        exit(ans);
      end else
      begin
        if i>id div 4 then ans:=ans+pow[i-1]*sw[i]*t
          else ans:=ans+pow[i]*sw[i];
      end;
    end;
  inc(ans);
  exit(ans);
end;
function solve(const upper:string):int64;
var ans:int64;
    k:longint;
begin
  ans:=0;
  for k:=0 to 15 do
    ans:=ans+solve2(upper,k,k)-solve2(upper,k,k-1);
  exit(ans);
end;
begin
  for i:=0 to 15 do num[list[i]]:=i;
  readln(q);
  for i:=1 to q do
  begin
    getstr(l);getstr(r);
    writeln(solve(r)-solve(l)+check(l));
  end;
end.