牛客多校2019-7H-Pair（两个数的数位DP）

Pair

考场上加了各种各样的优化也没能由T变AC。。。赛后题解“直接数位DP就行”

题意：给定 $A,B,C$A,B,C求满足。。。还是看下面的题目描述吧。

思路：

1. 直接数位DP就行，但需要注意的是！
2. 两个数的数位DP对于不保存的情况只有两个数都达到上限时，其余的都需要记忆化。比如一个数达到上限，另一个没有达到上限的情况。当然，也可以全部都保存下来，也不怎么费空间

题目描述：

Given three integers , Count the number of pairs $\&lt;x,y\&gt;$<x,y> (with $1\le x\le A$1≤x≤A and $1\le y\le B$1≤y≤B)
such that at least one of the following is true:
( $x$x and $y$y) $\&gt;$> $C$C
( $x$x xor $y$y) $\&lt;$< $C$C
(“and”, “xor” are bit operators)

输入描述:

The first line of the input gives the number of test cases, T (T≤100). test cases follow.
For each test case, the only line contains three integers , and .1≤A,B,C≤10^9

输出描述:

For each test case, the only line contains an integer that is the number of pairs satisfying the condition given in the problem statement.

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

int num[3][33];
ll dp[33][3][3][2][2][2][2];

void get_num(int a, int f) {
	int len=0;
	while(a) {
		num[f][len++]=a%2;
		a/=2;
	}
}

ll dfs(int pos, int state1, int state2, int f1, int f2, int first1, int first2) {
	if(pos<0) return !first1&&!first2&&(state1==0||state2==2);
	ll &ans=dp[pos][state1][state2][f1][f2][first1][first2];
	if(~ans) return ans;
	ans=0;
	int up1=f1?num[1][pos]:1;
	int up2=f2?num[2][pos]:1;
	for(int i=0; i<=up1; ++i) {
		for(int j=0; j<=up2; ++j) {
			int p1=i&j, p2=i^j;
			int new1=state1, new2=state2;
			if(state1==1) {
				if(p1<num[0][pos]) new1=2;
				else if(p1>num[0][pos]) new1=0;
			}
			if(state2==1) {
				if(p2<num[0][pos]) new2=2;
				else if(p2>num[0][pos]) new2=0;
			}
			ans+=dfs(pos-1,new1,new2,f1&&i==up1,f2&&j==up2,!i&&first1,!j&&first2);
		}
	}
    return ans;
}

int main() {
	//ios::sync_with_stdio(false);
    int T=read();
	while(T--) {
		int a=read(), b=read(), c=read();
		memset(dp,-1,sizeof(dp));
		memset(num,0,sizeof(num));
		get_num(a,1), get_num(b,2), get_num(c,0);
		printf("%lld\n", dfs(31,1,1,1,1,1,1));
	}
}