分析
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int xx[1100],yy[1100],cnt1,cnt2;
int dp[510][510][2];
inline int work(int a,int b,int s,int c){
int i,j,k,d=max(max(a-1,b),(int)log2(s)+1ll),x,y,z,g;
for(i=0;i<=d;i++)
for(j=0;j<=c;j++)
dp[i][j][0]=dp[i][j][1]=0;
i=0;
for(x=0;x<=1;x++)
for(y=0;y<=1;y++){
k=(x+y)>>1,z=(x+y)&1;
if(i==b-1&&!y)continue;
if(z!=(s&1))continue;
if(i>b-1&&y)continue;
if(i>a-2&&x)continue;
dp[i][x+y][k]++;
}
for(i=1;i<=d;i++)
for(j=0;j<=c;j++)
for(g=0;g<=1;g++)
if(dp[i-1][j][g])
for(x=0;x<=1;x++)
for(y=0;y<=1;y++){
k=(x+y+g)>>1,z=(x+y+g)&1;
if(i==b-1&&!y)continue;
if(z!=((s&(1ll<<i))?1:0))continue;
if(i>b-1&&y)continue;
if(i>a-2&&x)continue;
dp[i][j+x+y][k]+=dp[i-1][j][g];
}
return dp[d][c][0];
}
inline int sum(int x){
int res=x<<1;
while(x)res-=(x&1ll),x>>=1;
return res;
}
signed main(){
int x,y,z,d,c,i,j,k,t,x2,y2,s,a,b;
scanf("%lld",&t);
while(t--){
scanf("%lld%lld%lld%lld",&d,&x,&y,&c);
cnt1=cnt2=0;
x2=x,y2=y;
while(x2)xx[++cnt1]=(x2&1),x2>>=1;
while(y2)yy[++cnt2]=(y2&1),y2>>=1;
reverse(xx+1,xx+cnt1+1);
reverse(yy+1,yy+cnt2+1);
z=0;
for(i=1;i<=min(cnt1,cnt2);i++)
if(xx[i]==yy[i])z=(z<<1)+xx[i];
else break;
s=sum(x)+sum(y)-sum(z)-sum(z>>1);
if(c==1){
printf("%lld
",s);
continue;
}
int Ans=0;
for(a=0;a<d;a++)
for(b=0;b<d;b++){
int v=(1ll<<(a+1))+(1ll<<(b+1))-3;
z=s/v;
if(!z)continue;
if((int)log2(z)+max(a,b)+1>d)continue;
k=s-z*v;
for(i=0;i<=a+b;i++)
if((i+k)%2==0)Ans+=work(a,b,(i+k)>>1,i);
}
printf("%lld
",Ans-1);
}
return 0;
}