刷题记录:牛客NC15979小q的数列

传送门:牛客
是一道数学题,想不到规律可能有点自闭

题目描述
小q最近迷上了各种好玩的数列，这天，他发现了一个有趣的数列，其递推公式如下：
f[0]=0 f[1]=1;
f[i]=f[i/2]+f[i%2];(i>=2)
现在，他想考考你，问：给你一个n，代表数列的第n项，你能不能马上说出f[n]的值是多少，以及f[n]所代表的值第一次出现在数列的哪一项中？（这里的意思是：可以发现这个数列里某几项的值是可能相等的，则存在这样一个关系f[n’] = f[n] = f[x/2]+f[x%2] = f[x]…（n’<n<x） 他们的值都相等，这里需要你输出最小的那个n’的值)(n<10^18)

开始思路:
刚开始一看n最大值为10^18次方,感觉就要爆炸,直接递归感觉肯定不行,因此自己加了一点点的剪枝,想要"蒙混过关",没想到这道题卡的很紧,直接爆内存了,感觉很自闭,即使数组开了很小(100000),还是爆了.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
ll k[1000000];
ll f(ll num) {
	if(k[num]!=0||num==0) return k[num];
	if(num<1000000) {
		if(k[num/2]==0) {
			k[num/2]=f(num/2);
		}
		if(k[num%2]==0) {
			k[num%2]=f(num%2);
		}
		k[num]=k[num/2]+k[num%2];
		return k[num];
	}
}

int main() {
	ll t;cin>>t;
	ll a;
	memset(k,0,sizeof(k));
	k[0]=0;k[1]=1;
	for(ll i=1;i<=t;i++){
		a=read();
		ll kk=f(a);
		printf("%lld ",kk);
		for(ll j=0;j<=a;j++) {
			if(f(j)==kk) {
				printf("%lld\n",j);
			}
		}
	}
	return 0;
} 

然后自己手模了一下,发现这个数列是存在一定规律的
n f(n) n’ 二进制
0 0 0 0
1 1 1 1
2 1 1 10
​3 2 3 11
​4 1 1 100
​5 2 3 101
​6 2 3 110
​7 3 7 111
​8 1 1 1000
你会发现f(n)就是该数二进制下的1的个数,而最早的n’就是二进制下1<<(1的个数)-1的值,然后,焯!!,这么简单??

int main() {
	ll t;t=read();
	while(t--) {
		ll n;n=read();ll sum=0;
		while(n>0) {
			ll a=n%2;
			n/=2;
			if(a==1) {
				sum++;
			}
		}
		printf("%lld %lld\n",sum,(1ll<<sum)-1);
	}
}