[数据结构与算法]AtCoder ABC129E Sum Equals Xor 动态规划

题目传送门

Describtion

以二进制给定一整数 $L$ ，求有多少二元组 $(a,b)$ 满足 $a+b=a\oplus b\le L$ 。

Solution

对 $a,b$ 的二进制形式的每一位进行讨论。
因为异或是不进位加法，所以 $a+b=a\oplus b$ 相当于 $a$ 和 $b$ 的同一位不能同为 $1$。
令 $dp[i][0]$ 为 $a\oplus b$ 的前 $i$ 位小于 $L$ 的前 $i$ 位的方案数，$dp[i][1]$ 则为等于的方案数。

• $L$ 的当前位为 $1$。此时等于的情况为上一位等于且 $a,b$ 分别取 $1,0$ 和 $0,1$，即 $dp[i][1]=dp[i?1][1]\times 2$。小于的情况有两种：上一位小于，则有 $3$ 种情况:$0,0$，$0,1$和$1,0$ ；上一位等于的情况就 $1$ 种：$0,0$，即 $dp[i][0]=dp[i?1][0]\times 3+dp[i?1][1]$。
• $L$ 的当前位为 $0$。等于的情况为上一位等于且 $a,b$ 都取$0$，即 $dp[i][1]=dp[i?1][1]$。小于的情况只有 $3$ 种，即上一位小于，$a,b$ 分别取 $0,0$，$0,1$和$1,0$。

最终答案即为 $dp[n][1]+dp[n][0]$,$n$即为$L$的二进制长度。

Code

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
long long n,dp[105000][2];
char s[105000];
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	dp[0][1]=1;//初始化
	for(int i=1;i<=n;++i){
		dp[i][0]=(dp[i-1][0]*3)%mod;
		if(s[i]=='1'){
			dp[i][0]=(dp[i][0]+dp[i-1][1])%mod;
			dp[i][1]=(dp[i-1][1]*2)%mod;
		}
		else dp[i][1]=dp[i-1][1];
	}
	printf("%lld\n",(dp[n][0]+dp[n][1])%mod);
	return 0;
}