[ICPC2021上海站]Sum of Log（数位DP）

题目链接：C-Sum of Log_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海） (nowcoder.com)

题意

求一个式子的值。

$$ \sum\limits_{i = 0}^{X} \sum\limits_{j=[i=0]}^{Y} [i \& j==0] \lfloor log(i + j) + 1 \rfloor$$

分析

不难发现，当满足条件\([i \& j == 0]\)时，\(i + j\)不会产生进位，所以\(log_{2}(i + j) + 1\)就是\(i || j\)的二进制最高位的位置。比如\(i + j = (100010)_2\)，那么这个\(log_{2}(i + j) + 1 = 6\)。

然后又想到这个log值的取值其实并不多，在1e9的范围内也就30个左右。

所以我们可以枚举这个log值，然后进行数位dp算出最高位为k的满足条件的数字的个数，然后乘上这个log值即可，当然枚举的方式并不是简单的for循环，需要在dp过程中进行枚举，方式是将满足条件的数字的贡献加到答案里。

当上一位还没有1，而这一位产生了1，那么就可以确定最高位就是当前位，就可以将（当前位 * 满足调价的个数）加到答案里。

值得注意的是在每个样例开始前要将a，b数组清空，因为这是同时对两个数位进行dp，起始位置是\(max(pa, pb)\)，所以可能产生另一个数某些位置的数据失真。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 100, p = 1e9 + 7;

int a[maxn], b[maxn];
int dp[maxn][2][2][2];


int dfs(int pos, bool la, bool lb, bool st, int &ans)//st表示计数是否开始了
{
	if(pos == 0)return 1;
	if(dp[pos][la][lb][st] != -1)return dp[pos][la][lb][st];
	
	int up1 = la ? a[pos] : 1;
	int up2 = lb ? b[pos] : 1;
	int res = 0;
	for(int i = 0;i <= up1; ++ i)
	for(int j = 0;j <= up2; ++ j)
	{
		if((i & j) != 0)continue;
		
		int tmp = dfs(pos - 1, la && (i == up1), lb && (j == up2), st || i || j, ans);
		if(!st && (i || j))ans = (ans + tmp * pos) % p;
		
		res = (res + tmp) % p;
	}
	
	return dp[pos][la][lb][st] = res;
}

int solve(int x, int y)
{
	memset(a, 0, sizeof a);
	memset(b, 0, sizeof b);
	memset(dp, -1, sizeof dp);
	
	int pa = 0, pb = 0;
	while(x)a[++ pa] = x & 1, x >>= 1;
	while(y)b[++ pb] = y & 1, y >>= 1;
	int ans = 0;
	dfs(max(pa, pb), true, true, false, ans);
	return ans;
}

signed main()
{
	int _;scanf("%lld", &_);
	while(_ --)
	{
		int x, y;scanf("%lld %lld", &x, &y);
		printf("%lld\n", solve(x, y));
	}	
	return 0;
}