自动搬运

查看原文

来自洛谷，原作者为

	xuyimeng Carlitos ^-^

搬运于2025-08-24 22:17:40，当前版本为作者最后更新于2025-02-17 20:57:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析

打个表或者通过直觉不难发现：新的数要在已有符合条件数的前面加1构造得到。因为10=5*2，在前面加数才能保证后面十进制和二进制的关系不被破坏。

我们考虑取出一个已经符合条件的数在前面添上1进行更新：

十进制: $\overline{A}(i位)+\overline{100...0}(i位0)=\overline{1A}$
二进制: $\overline{XA}(i位)+\overline{Y0...00}(i位0)=\overline{ZA}$
因为$10^i=5^i\times2^i$，所以$Y\&1=1$，十进制为二进制后缀当且仅当$X\&1=0$，即$(A>>i)\&1=0$，此时将$A$计入答案即可
否则，$(A>>i)\&1=1$，当前这个数$A$就不能通过$+10^k(k>i)$构造出新的合法数了。因为$A+10^k$十进制下第i位为$0($因为$i<k)$，二进制下$A$第$i$位为$1($即$(A>>i)\&1=1)$，$10^k$第$i$位为$0($同上$)$，相加得$1$，不可能成立，标记一下，下次枚举到时跳过即可。

总体复杂度$O(nl)$

代码实现

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=10003;
int n,m=1,M,f[N];//f[i]:上文提到的标记第i个答案是否能够生成新的答案
struct Bigint {//高精
	int len;
	vector <int> num;
	Bigint()=default;
	void clear(int size) {
		num.clear();
		num.resize(size+1);
		len=size;
	}
}d[N],p,tmp;
//d[i]:第i个符合要求的数
Bigint Bigint_add(const Bigint &a, const Bigint &b) {//高精加高精  
	Bigint res;
	res.clear(max(a.len,b.len)+1);
	for(int i=1; i<res.len; i++) {
		res.num[i]+=(i<=a.len?a.num[i]:0)+(i<=b.len?b.num[i]:0);
		if(res.num[i]>=10) {
			res.num[i+1]+=res.num[i]/10;
			res.num[i]%=10;
		}
	}
	while(res.len>1&&res.num[res.len]==0) res.len--, res.num.pop_back();
	return res;
}
Bigint Bigint_div2(Bigint a) {//高精右移操作  
	for(int i=a.len; i>=1; i--) {
		if(a.num[i]&1) a.num[i-1]+=10;
		a.num[i]>>=1;
	}
	if(a.len>1&&a.num[a.len]==0) a.len--, a.num.pop_back();
	return a;
}
Bigint Bigint_upd(const Bigint &a) {//更新p 相当于乘10
	Bigint res;
	res.clear(a.len+1);
	for(int i=1;i<res.len;i++) res.num[i]=0;
	res.num[res.len]=1;
	return res;
}
void print(const Bigint &a) {//高精输出
	for(int i=a.len;i>=1;i--) printf("%d",a.num[i]);
	return;
}
int main() {
	scanf("%d",&n);
	d[0].clear(1); d[0].num[1]=0;//0不计入总数 但可以用于更新
	d[1].clear(1); d[1].num[1]=1;
	p.clear(1); p.num[1]=1;
	for(int i=1;m<n;i++) {
		p=Bigint_upd(p);
		M=m;
		for(int j=0;j<=M;j++) {
			if(f[j]) continue;
			tmp=d[j];
			for(int k=1;k<=i;k++) tmp=Bigint_div2(tmp);//右移i位
			if(tmp.num[1]&1) f[j]=1;
			else {
				d[++m]=Bigint_add(d[j],p);
				if(m==n) break;
			}
		}
	}
	print(d[m]);
	return 0;
}

我知道我排版很丑 语言表达也很烂 不要喷我qwq