链接:https://ac.nowcoder.com/acm/contest/887/H
来源:牛客网
题目描述:
给定A, B, C, 需要求有多少个pair<x,y> 满足(1<x<=A并且1<y<=B) • x & y > C or x ^ y < C 解题思路:假设状态dp【pos】【sta1】【sta2】【lim1】【lim2】为,在二进制下,长度为pos的时候,第一个条件为sta1,第二个条件为sta2,X的限制状态为lim1,Y的限制状态为lim2时的方案数。当sta1或者sta2为0时还不确定是否满足条件,为1时满足条件,为2时不满足条件。最后减去X,或者Y为零时不合法的方案数就好了。#include<bits/stdc++.h> using namespace std; typedef long long ll; ll dp[34][3][3][3][3]; int num1[34],num2[34],num3[34]; int len; ll dfs(int pos,int sta1,int sta2,int lim1,int lim2){ // cout<<pos<<endl; if(pos==-1){ return (sta1==1||sta2==1); } if(~dp[pos][sta1][sta2][lim1][lim2])return dp[pos][sta1][sta2][lim1][lim2]; if(sta1==2&&sta2==2){ return dp[pos][sta1][sta2][lim1][lim2]=0; } if(sta1==1||sta2==1){ ll a=0; ll b=0; if(lim1){ for(int i=pos;i>=0;i--){ if(num1[i]==1){ a+=(1<<i); } } a++; } else a=pow(2,pos+1); if(lim2){ for(int i=pos;i>=0;i--){ if(num2[i]==1){ b+=(1<<i); } } b++; }else b=pow(2,pos+1); return dp[pos][sta1][sta2][lim1][lim2]=(a)*(b); } int up1=lim1?num1[pos]:1; int up2=lim2?num2[pos]:1; ll ans=0; for(int i=0;i<=up1;i++){ for(int j=0;j<=up2;j++){ int op1=i&j; int op2=i^j; int st1; int st2; if(op1>num3[pos])st1=1; else if(op1==num3[pos])st1=0; else st1=2; if(op2<num3[pos])st2=1; else if(op2>num3[pos])st2=2; else st2=0; if(sta1==1)st1=1; else if(sta1==2)st1=2; if(sta2==1)st2=1; else if(sta2==2)st2=2; ans+=dfs(pos-1,st1,st2,lim1&&i==up1,lim2&&j==up2); } } dp[pos][sta1][sta2][lim1][lim2]=ans; return ans; } int main(){ int t; int a,b,c; scanf("%d",&t); while(t--){ memset(dp,-1,sizeof(dp)); memset(num1,0,sizeof(num1)); memset(num2,0,sizeof(num2)); memset(num3,0,sizeof(num3)); scanf("%d%d%d",&a,&b,&c); int len1,len2,len3; len1=len2=len3=0; int aa,bb,cc; aa=a; bb=b; cc=c; while(a){ num1[len1++]=a&1; a/=2; } while(b){ num2[len2++]=b&1; b/=2; } while(c){ num3[len3++]=c&1; c/=2; } len=max(len1,max(len2,len3)); ll ans=dfs(len-1,0,0,1,1); printf("%lld\n",ans-min(aa,cc-1)-min(bb,cc-1)-1); } return 0; }