2 条题解
-
0
#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)); } } -
0
huangzheng
LV 6
@ 2025-10-8 17:11:42
#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)); } }
- 1
