[HNOI2002Kathy函数]数位DP

    xiaoxiao2021-03-26  7

    题目描述

    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位的二进制数也只要确定 [(2n1)/2]+1=n ,即它们所要确定的二进制数位数相等。   设 m=[(n1)/2] ,则当n为偶数时( n1 为奇数),满足条件的二进制数且位数 n 的一共有 2m2+2m2 个。奇数时一共有 2m22 个。   下面来考虑位数正好为n时的情况。首先,若n为奇数可以把它看做n+1来处理。我们只考虑第2~mid位。若当前正考虑第k位,若它为1那么我们构造一个二进制数——第k位为0,前k-1位与这个数相同,那么后面的数字可以任意取;否则不管。但这样的话,我们就忽略了一种情况,那就是可以取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; }

    ^_^

    转载请注明原文地址: https://ju.6miu.com/read-650154.html

    最新回复(0)