题目链接: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; }
文章评论