题目描述
Tiger非常喜欢数学，所以他参加了学校组织的数学课外兴趣小组。在兴趣小组的学习当中，老师向Tiger介绍了Kathy函数，Kathy函数是这样定义的： f(1)=1 f(3)=3 f(2n)=f(n) f(4n+1)=2f(2n+1)−f(n) f(4n+3)=3f(2n+1)−2f(n) Tiger对Kathy函数产生了浓厚的兴趣，他通过研究发现有很多的数n都满足 。 对于一个给定的数m，他希望你求出所有的满足 的自然数n的个数，其中 f(n)=n(n<=m) 分析：
首先，由题目中出现的2,4大胆推测二进制方面的规律，发现只要这个数的二进制是对称的，那么就满足条件。 设这个二进制数有n位。 我们来构造满足条件的二进制数：显然，我们只要确定二进制数的一半n/2（当n为偶数时）或[n/2]+1（当n为奇数时），则由对称性，另一半也就确定了。我们先不考虑构造的二进制为n位的（即1~n-1位）。然后我们发现，1位的与2位的、3位的与4位的等二进制数它们的满足条件的方法数是一样的。这也是可以证明的：设两个二进制数分别为2n和2n-1位的，2n位的二进制数只要确定n位，而2n-1位的二进制数也只要确定 [(2n−1)/2]+1=n ，即它们所要确定的二进制数位数相等。 设 m=[(n−1)/2] ，则当n为偶数时( n−1 为奇数)，满足条件的二进制数且位数 ＜n 的一共有 2m∗2+2m−2 个。奇数时一共有 2m∗2−2 个。 下面来考虑位数正好为n时的情况。首先，若n为奇数可以把它看做n+1来处理。我们只考虑第2~mid位。若当前正考虑第k位，若它为1那么我们构造一个二进制数——第k位为0，前k-1位与这个数相同，那么后面的数字可以任意取；否则不管。但这样的话，我们就忽略了一种情况，那就是可以取１的时候。因此，当从中间数起，右边的第一个与左边对应不相同的数字为a,它对应的数字为b，若a>b或者不存在这样的a,b则方案数加1。
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int maxn=1010; char st[maxn]; int n; struct Bigint{ int s[maxn]; void clear(){ memset(s,0,sizeof(s)); } void operator =(int val){ clear(); while(val){ s[++s[0]]=val%10; val/=10; } return; } void operator =(const char *str){ int len=strlen(str); s[0]=len; for(int i=0;i<len;i++) s[s[0]-i]=str[i]-'0'; } void maintain(){ for(int i=1;i<=s[0];i++) if(s[i]>=10) s[i+1]+=s[i]/10,s[i]%=10; while(s[s[0]+1]){ s[0]++; s[s[0]+1]=s[s[0]]/10; s[s[0]]%=10; } } void operator +=(const int &A){ s[1]+=A; maintain(); } void operator +=(Bigint A){ s[0]=max(s[0],A.s[0]); for(int i=1;i<=s[0];i++) s[i]+=A.s[i]; maintain(); } void operator -=(const int &A){ int i=1; s[i]-=A; while(s[i]<0){ while(s[i]<0)s[i]+=10,s[i+1]--; i++; } if(!s[s[0]]) s[0]--; } int mod(){ return s[1]&1; } void div(){ for(int i=s[0];i>=1;i--){ if(i>1 && s[i]&1) s[i-1]+=10; s[i]>>=1; } if(!s[s[0]]) s[0]--; } void mul(){ for(int i=1;i<=s[0];i++) s[i]*=2; maintain(); } void print(){ for(int i=s[0];i>=1;i--){ printf("%d",s[i]); } puts(""); } }ans,res,num; int b[maxn*maxn]; int main(){ scanf("%s",st); num=st; n=0; while(num.s[0]){ b[n++]=num.mod(); num.div(); } if(n>1){ int mid=(n-1)>>1; ans=3-(n&1); for(int i=0;i<mid;i++) ans.mul(); ans-=2; res.clear(); for(int i=n-2;i>=n-mid-1;i--) res.mul(),res+=b[i]; bool flag=true; for(int i=mid;i>=0;i--) if(b[i]!=b[n-i-1]){flag=(b[i]>b[n-i-1]);break;} if(flag) res+=1; ans+=res; }else ans=n; ans.print(); return 0; }^_^
