CodePlus7 神秘序列

没错，就找到这样一种方法之后二分+模拟即可。
卡时间可以去$OEIS$OEIS搜一波发现$\frac {n^2}{n+k}\sim\pi$n+kn2​∼π
然后就可以$O(n)$O(n)过掉这题了。

$\mathcal AC \ Code$AC Code

#include<bits/stdc++.h>
#define LL long long
#define Pi 3.1415926535897932384626433832795
using namespace std;

LL K,a[3333333];
int calc(LL n){
	LL t = n + K;
	memset(a,0,(n+1)*8);
	for(int i=1;i<=n && t;i++){
		LL p = (t-1)%(i+1);	
		a[i] = i - p;
		t -= (t+i) / (i+1);
	}
	return t;
}

char cb[1<<22],*cs=cb;

template<class T>void print(T a){
	static int q[22]={};
	for(;a;a/=10) q[++q[0]] = a%10;
	if(!q[0]) putchar('0');
	for(;q[0];) putchar(q[q[0]--]+'0');
	putchar('\n');
}

int main(){

	freopen("p3.in","r",stdin);
	freopen("p3.out","w",stdout);
	scanf("%lld",&K);
	int N = round((Pi + sqrt(Pi * Pi + 4.0 * K * Pi)) / 2);
	int L = max(1,N-4) , R = N+4 , mid;
	for(;L<R;){
		int mid = (L+R)>>1;
		int t =calc(mid);
		if(t) L = mid + 1;
		else if(a[mid]){
			L = mid;
			break;
		}
		else R = mid - 1;
	}
	calc(L);
	print(L);
	for(int i=1;i<=L;i++)
		print(a[i]);
}