程序员是不是都是做网站的,网站建设制作设计珠海,如何注册企业邮箱免费,什么样的网站需要备案添加链接描述 题意#xff1a;对于给定的n,m 。计算0~n 每一个数和m 之后#xff0c;得到的数 的二进制中 1的个数的和。
一位一位的算。最多是60位。 我们只需要计算 在 1-n这些数上#xff0c;有多少个数 第i位 为1. 因为是连续的自然数#xff0c;每一位上1 的…添加链接描述 题意对于给定的n,m 。计算0~n 每一个数和m 之后得到的数 的二进制中 1的个数的和。
一位一位的算。最多是60位。 我们只需要计算 在 1-n这些数上有多少个数 第i位 为1. 因为是连续的自然数每一位上1 的出现 必然存在某种规律。 我们从 第零位 开始计数。 第 i 位 的 1 的出现周期是 2^(i1) 其中前一半是0后一半是1.数量是 2^i个 想明白这一点之后 对于整除的那一部分第i位的贡献是
int w(long long )1i;
n/(w*2)*w 那么整的部分算完了接下来算 散 的那一部分
这里可以自己找个例子算一下。不然很容易错。
max((long long )0,n%(2*w)-w1)#include bits/stdc.h
using namespace std;
#define int long long
const int mod998244353;
signed main()
{int n,m;cinnm;int ans0;for (int i0;i60;i){if (mi 1){int w(long long )1i;ansn/(w*2)*wmax((long long )0,n%(2*w)-w1);ans%mod;}}coutansendl;return 0;
}可以注意到 ai的数值非常小不到1e6这个时候 就有很大可能 开数值桶。
#include bits/stdc.h
#define int long long
using namespace std;
const int wc1e65;
int a[wc],s[wc];signed main()
{int n;cinn;int t0;for (int i0;in;i){cint;a[t];}for (int i1;iwc;i){s[i]s[i-1]a[i];}int ans0;for (int i1;iwc;i){ansa[i]*(a[i]-1)/2;//选择两个相同的数的贡献//枚举左端点 比枚举右端点好因为右端点不一定正好到wc//后面可能还有一些比a[i]大的数 for (int ji;jwc;ji){ansa[i]*(j/i)*(s[min(wc,ji-1)]-s[ji?i:j-1]);非常优美的代码^_^} }coutans\n;return 0;
}时间复杂度 第二层for里面因为每次都是 i 的倍数并且有一个上界 wc所以是调和级数的复杂度 复杂度为 log wc。 总的复杂度为 wc* log wc
