LUOGU P6034 Ryoku与最初之人笔记简要题解

比赛的时候有个地方忘记取模怒砍80，调了一下午Orz（虽然我总共貌似就打这个比赛半个多小时

我们一眼看到涉及到公约数/同余和 xor，所以我们想到了一些关于xor的性质

a+b >= a xor b >= b-a （b>a)，而且ab不相等所以就是求a xor b = b - a的数对数

但是我们看到n<=1e18，这玩意怎么求？？？

我们从异或的性质入手发现a xor b = b - a的充要条件就是a & b = b

也就是我们考虑a,b作为两个二进制集合，则a是b的真子集

然后我们发现就是求Σ2^popcount(i)-1，这个好像是数位DP的套路，但是我怎么会数位DP

于是我找了一波规律

i 　　　　0 1 2 3 4 5 6 7

pop　　 0 1 1 2 1 2 2 3

value　　0 1 1 3 1 3 3 7

发现这个数列是个类似分形的东西，每次把pop复制到后面再整体+1，然后我就觉得可以搞

这个玩意又像倍增又像二分又像分治（但是又啥都不像（其实像格雷码

我们预处理出前(1<<k)个数的贡献和，然后用一个变量cnt来记录此前的popcount，我们发现cnt对答案的贡献是可以暴力计算的，于是就做完了（雾

这个玩意虽然写了一堆但是思路肥肠好想

我好像写的不是正解，因为他们算贡献直接用子集的子集就给整出来了

时间复杂度O(log^2 N)

代码：

#include <cstdio>

#include <iostream>

using namespace std;

#define int long long int

inline int read() {

	int x=0,f=1;

	char cr=getchar();

	while (cr>'9' || cr<'0') {

		if (cr=='-') f=-1;

		cr=getchar();

	}

	while (cr>='0' && cr<='9') {

		x=(x<<3)+(x<<1)+cr-'0';

		cr=getchar();

	}

	return x*f;

}

const int mod=1e9+7;

int ans[70];

inline void init() {

	ans[0]=0;

	for (int i=1;i<=63;i++) ans[i]=(ans[i-1]*3ll+(1ll<<i-1ll))%mod;

}

inline int calc(int cnt,int num) {

	int val=ans[num];

	while (cnt--) val*=2ll,val+=(1ll<<num),val%=mod;

	return val;

}

signed main() {

	init();

	int n=read();

	int res=0,cnt=0;

	for (int i=63;i>=0;i--) {

		if (n&(1ll<<i)) {

			res+=calc(cnt,i),res%=mod;

			cnt++;

		}

	}

	res+=(1ll<<cnt)-1ll,res%=mod;

	printf("%lld",res);

}

巴特西

LUOGU P6034 Ryoku与最初之人笔记简要题解

最新文章

热门文章

巴特西

LUOGU P6034 Ryoku与最初之人笔记 简要题解

最新文章

热门文章

LUOGU P6034 Ryoku与最初之人笔记简要题解