1223: [HNOI2002]Kathy函数
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 207 Solved: 90
[Submit][Status]
Description
Input
仅有一行，为正整数m
Output
输出仅有一个正整数，表示所有的满足f(n)=n,(n<=m) 的自然数的个数。
Sample Input
5
Sample Output
3
这道题的高精度模板相对又有完善，但还存在bugs，使用时尽量讲位数多开几倍。
这道题由于递归方程转移有2、4，所以应该往二进制那边去想，可以通过归纳法证明f(n)=n当且仅当n二进制为回文串（相当神奇），然后就是数位DP，最开始我将数据范围想成了m<=2^100，还说刚好long long可以存，但是10^100就必须写高精了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<unistd.h> using namespace std; typedef long long qword; #define MAXN 20100 class number//四位 { public: const static int max_val=10000; const static int max_len=100; number() { clear(); } number(int x) { *this=x; } bool is_odd()const { return numb[0]%2==1; } bool is_even()const { return numb[0]%2==0; } int size()const { return topn; } int length()const { int x=numb[topn]; int ret=0; while (x) { ret++; x/=10; } int y=0; x=number::max_val; while (x) { y++; x/=10; } y--; ret+=topn*y; return ret; } number pow(int x)const { number ret,a; a=*this; ret=1; while (x) { if (x&1)ret=ret*a; a=a*a; x>>=1; } return ret; } void operator =(int x)//{{{ { int now=0; clear(); numb[now]=x; while (numb[now]>=number::max_val) { numb[now+1]+=numb[now]/number::max_val; numb[now]%=number::max_val; now++; if (now>topn)topn=now; } }//}}} void operator =(number num) { topn=num.topn; memcpy((this->numb),num.numb,sizeof(num.numb[0])*(topn+1)); } void operator +=(number num)//{{{ { int i; topn=max(topn,num.topn); for (i=0;i<=topn;i++) { numb[i]+=num.numb[i];; if (numb[i]>=number::max_val) { numb[i+1]+=numb[i]/number::max_val; numb[i]%=number::max_val; } } while (numb[topn+1]) { topn++; numb[topn+1]+=numb[topn]/number::max_val; numb[topn]%=number::max_val; } }//}}} void operator +=(int x)//{{{ { int now=0; if (topn==-1)topn=0; numb[now]+=x; while (numb[now]>=number::max_val) { numb[now+1]+=numb[now]/number::max_val; numb[now]%=number::max_val; now++; if (now>topn)topn=now; } }//}}} void operator *=(int x)//{{{ { int i; for (i=0;i<=topn;i++) { numb[i]*=x; } for (i=0;i<=topn;i++) { if (numb[i]>=number::max_val) { numb[i+1]+=numb[i]/number::max_val; numb[i]%=number::max_val; } } while (numb[topn+1]) { topn++; numb[topn+1]+=numb[topn]/number::max_val; numb[topn]%=number::max_val; } }//}}} void operator -=(number &num)//{{{ { if (*this<num)throw "Error! ->void operator -=(number &num) "; int i; for (i=0;i<=topn;i++) { numb[i]-=num.numb[i]; } for (i=0;i<=topn;i++) { while (numb[i]<0) { numb[i]+=number::max_val; numb[i+1]--; } } while (topn&&!numb[topn])topn--; }//}}} void operator --(int)//{{{ { if (topn==0&&numb[0]==0)throw "Error! ->void operator --(int) "; int now=0; numb[now]--; while (numb[now]<0) { numb[now+1]--; numb[now]+=number::max_val; } while (topn&&!numb[topn])topn--; }//}}} private: int numb[max_len]; int topn; void clear() { topn=0; memset(numb,0,sizeof(numb)); } friend bool operator <(number num1,number num2); friend bool operator <=(number num1,number num2); friend bool operator ==(number num1,number num2); friend ostream& operator <<(ostream &out,number num); friend istream& operator >>(istream &in,number &num); friend number operator *(number num1,number num2); friend number operator *(number num,int x); friend number operator +(number num1,number num2); //a=a+b远没有a+=b快 }; bool operator <(number num1,number num2)//{{{ { if (num1.topn!=num2.topn) { return num1.topn<num2.topn; } int i; for (i=num1.topn;i>=0;i--) { if (num1.numb[i]!=num2.numb[i]) { return num1.numb[i]<num2.numb[i]; } } return false; }//}}} bool operator <=(number num1,number num2)//{{{ { if (num1.topn!=num2.topn) { return num1.topn<num2.topn; } int i; for (i=num1.topn;i>=0;i--) { if (num1.numb[i]!=num2.numb[i]) { return num1.numb[i]<num2.numb[i]; } } return true; }//}}} bool operator ==(number num1,number num2)//{{{ { if (num1.topn!=num2.topn)return false; for (int i=0;i<=num1.topn;i++) { if (num1.numb[i]!=num2.numb[i])return false; } return true; }//}}} ostream& operator <<(ostream &out,number num)//{{{ { int i; out<<num.numb[num.topn]; for (i=num.topn-1;i>=0;i--) { //压六位时 //if (num.numb[i]<100000)out<<"0"; //if (num.numb[i]<10000)out<<"0"; if (num.numb[i]<1000)out<<"0"; if (num.numb[i]<100)out<<"0"; if (num.numb[i]<10)out<<"0"; out<<num.numb[i]; } return out; }//}}} istream& operator >>(istream &in,number &num)//{{{ { string str; in>>str; int i; num.clear(); for (i=(int)str.length()-1,num.topn=0;i>=0;i-=4,num.topn++) { if (i-3<(int)str.length()) { num.numb[num.topn]=(str[i]-'0')+10*(str[i-1]-'0')+100*(str[i-2]-'0')+1000*(str[i-3]-'0'); }else { if (i-2<(int)str.length())num.numb[num.topn]+=100*(str[i-2]-'0'); if (i-1<(int)str.length())num.numb[num.topn]+=10*(str[i-1]-'0'); if (i<(int)str.length())num.numb[num.topn]+=(str[i]-'0'); } } num.topn--; return in; }//}}} number operator *(number num,int x)//{{{ { number ret; ret=num; ret*=x; return ret; }//}}} number operator *(number num1,number num2) { number ret; ret.topn=num1.topn+num2.topn; for (int i=0;i<=num1.topn;i++) for (int j=0;j<=num2.topn;j++) { ret.numb[i+j]+=num1.numb[i]*num2.numb[j]; ret.numb[i+j+1]+=ret.numb[i+j]/number::max_val; ret.numb[i+j]%=number::max_val; } for (int i=0;i<=ret.topn;i++) { ret.numb[i+1]+=ret.numb[i]/number::max_val; ret.numb[i]%=number::max_val; } while (ret.numb[ret.topn+1]) { ret.topn++; ret.numb[ret.topn+1]+=ret.numb[ret.topn]/number::max_val; ret.numb[ret.topn]%=number::max_val; } while (ret.topn && !ret.numb[ret.topn]) { ret.topn--; } return ret; } number operator +(number num1,number num2)//{{{ { number ret; ret=num1; ret+=num2; return ret; }//}}} char str[MAXN]; int num0[MAXN]; bool num[MAXN]; number rec[MAXN][2][2]; int n,m; number search_m(int now,int fl,int bo) { int x,y; x=now-1;y=n-now; if (x>y) { number ret; ret=(int)(fl || (!fl && !bo)); return ret; } number &res=rec[now][fl][bo]; number aa; if (aa<rec[now][fl][bo])return res; res=0; if (!fl) { if (num[y]) { //1 if (num[x]==1) res+=search_m(now+1,false,bo);//1 else res+=search_m(now+1,false,true);//1 if (now>1)//首位非0 { if (num[x]==1) res+=search_m(now+1,true,false);//0 else res+=search_m(now+1,true,bo);//0 } }else if (!num[y]) { if (now>1)//特殊处理m==0情况 { if (num[x]==1) res+=search_m(now+1,false,false);//0 else res+=search_m(now+1,false,bo);//0 } } }else { res+=search_m(now+1,true,true);//1 res+=search_m(now+1,true,true);//0 } return res; } int main() { //freopen("input.txt","r",stdin); scanf("%s ",str); int i,j,x,y; n=strlen(str); x=y=-1; for (i=n-1;i>=0;i-=4) { x++; for (j=max(0,i-3);j<=i;j++) num0[x]=num0[x]*10+str[j]-'0'; } n=x+1; x=0; while (~n) { num[x++]=num0[0]%2; for (i=n-1;i>=0;i--) { if (i)num0[i-1]+=(num0[i]&1)*10000; num0[i]/=2; } while (n>=0 && !num0[n-1])n--; } n=x; /*for (i=n-1;i>=0;i--) { printf("%d",num[i]); } printf(" ");*/ /*for (i=0;i<=n;i++) for (j=0;j<2;j++) for (k=0;k<2;k++) rec[i][j][k]=-1;*/ number ans; ans=search_m(1,false,false); number xx; for (i=1;i<n;i++) { xx=2; xx=xx.pow((i-1)/2); ans+=xx; } cout<<ans<<endl; return 0; }