Pair-数位DP

题目链接

pair

题目描述

给出三个数字A,B,C。要你从1-A中取一个x，从1-B中取一个y。找出共有多少对(x,y)满足以下至少一个条件
1.x&y>c;
2.x^y<c;

思路

比赛的时候以为是数论知识，看了题解发现是数位DP，把A,B都转化为二进制，然后用二维的数位DP写。
dp[pos][and][xor][limit1][limit2]表示第pos位的数上 取和 以及取 异或 的情况。
Note：任何二进制的数位DP，都不能忽略前缀0，所以在统计完答案后，需要减去由于前缀0而产生的贡献。
所以还需要添加二维变成dp[pos][and][xor][limit1][limit2][zero1][zero2];
也可以用数学方法推出来多余的数。实际上应该等于ans=min(a,c-1)+min(b,c-1)+1(不会证明)；

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[32][3][3][2][2][2][2];
int a[32],b[32],c[32];
ll dfs(int pos,int And,int Xor,bool limit1,bool limit2,bool zero1,bool zero2)
{
	if(pos==-1)
	{
		if((And==1||Xor==2)&&zero1&&zero2)return 1ll;
		return 0;
	}
	if(dp[pos][And][Xor][limit1][limit2][zero1][zero2]!=-1)
	return dp[pos][And][Xor][limit1][limit2][zero1][zero2];
	int up1 = limit1?a[pos]:1;
	int up2 = limit2?b[pos]:1;
	ll temp = 0;
	for(int i=0;i<=up1;i++)
	{
		for(int j=0;j<=up2;j++)
		{
			int A=And,B=Xor;
			int x=i&j;
			int y=i^j;
			if(And==0)
			{
				if(x>c[pos])A=1;
				else if(x<c[pos])A=2;
			}
			if(Xor==0)
			{
				if(y>c[pos])B=1;
				else if(y<c[pos])B=2;
			}
 			temp+=dfs(pos-1,A,B,(i==up1)&&limit1,(j==up2)&&limit2,i==1||zero1,j==1||zero2);
		}
	}
	dp[pos][And][Xor][limit1][limit2][zero1][zero2]=temp;
	return temp;
}
ll solve(ll x,ll y,ll z)
{
	for(int i=0;i<30;i++)
	{
		a[i]=(x&1);x>>=1;
		b[i]=(y&1);y>>=1;
		c[i]=(z&1);z>>=1;
	}
	return dfs(29,0,0,1,1,0,0);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(dp,-1,sizeof(dp));
		ll A,B,C;
		cin>>A>>B>>C;
		cout<<solve(A,B,C)<<endl;
	}
}

总结

枚举数的时候，要切记前导零