[ICPC2021上海站]Sum of Log(数位DP)

发布于 2022-11-21  287 次阅读


题目链接: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-11-21