二进制、数位dp：0912T3

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132840291

考虑题目转化，二进制下满足 $i\subseteq j,(i+x)\subseteq (j+y)$

这显然是个数位dp形式

考虑枚举每一位与进位， $dp_{k,p_1,p_2}$ 表示第 $k-1$ 位向第 $k$ 位，分别进位 $p_1,p_2$ 的方案数

考虑当前 $(i,j)$ 二进制下分别为 $q_1,q_2$ ，则 $(i+x,j+y)=(p_1+q_1+x_i,p_2+q_2+y_i)=(n_1,n_2)$

必须满足 $q1\subseteq q2,n1\&1\subseteq n2\&1$ ，由 $dp(i+1,\frac{n_1}2,\frac{n_2}2)$ 转移过来

综上：

$$\Large dp(k,i,j)=\sum_{q1\subseteq q2,n1=p1+q1+x_i,n2=p2+q2+y_i}[n1\&1\subseteq n2\&1]dp(i+1,\frac{n_1}2,\frac{n_2}2)$$

dp[n][0][0].a[1]=1; 
for(i=n-1; i>=0; --i) {
	for(p1=0; p1<=1; ++p1) for(p2=0; p2<=1; ++p2) {
		for(q1=0; q1<=1; ++q1) for(q2=q1; q2<=1; ++q2) {
			n1=p1+q1+x[i]; n2=p2+q2+y[i]; 
			if(n1%2>n2%2) continue; 
			dp[i][p1][p2]=dp[i][p1][p2]+dp[i+1][n1/2][n2/2]; 
		}
	}
	
}
dp[0][0][0].print();