bzoj 1223: [HNOI2002]Kathy函数数位DP 高精度

1223: [HNOI2002]Kathy函数

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 207 Solved: 90
[Submit][Status]

Description

Input

仅有一行，为正整数m

Output

输出仅有一个正整数，表示所有的满足f(n)=n,(n<=m) 的自然数的个数。

Sample Input

Sample Output

　　这道题的高精度模板相对又有完善，但还存在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=;

                const static int max_len=;

                number()

                {

                        clear();

                }

                number(int x)

                {

                        *this=x;

                }

                bool is_odd()const

                {

                        return numb[]%==;

                }

                bool is_even()const

                {

                        return numb[]%==;

                }

                int size()const

                {

                        return topn;

                }

                int length()const

                {

                        int x=numb[topn];

                        int ret=;

                        while (x)

                        {

                                ret++;

                                x/=;

                        }

                        int y=;

                        x=number::max_val;

                        while (x)

                        {

                                y++;

                                x/=;

                        }

                        y--;

                        ret+=topn*y;

                        return ret;

                }

                number pow(int x)const

                {

                        number ret,a;

                        a=*this;

                        ret=;

                        while (x)

                        {

                                if (x&)ret=ret*a;

                                a=a*a;

                                x>>=;

                        }

                        return ret;

                }

                void operator =(int x)//{{{

                {

                        int now=;

                        clear();

                        numb[now]=x;

                        while (numb[now]>=number::max_val)

                        {

                                numb[now+]+=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[])*(topn+));

}

void operator +=(number num)//{{{

{

        int i;

        topn=max(topn,num.topn);

        for (i=;i<=topn;i++)

        {

                numb[i]+=num.numb[i];;

                if (numb[i]>=number::max_val)

                {

                        numb[i+]+=numb[i]/number::max_val;

                        numb[i]%=number::max_val;

                }

        }

        while (numb[topn+])

        {

                topn++;

                numb[topn+]+=numb[topn]/number::max_val;

                numb[topn]%=number::max_val;

        }

}//}}}

void operator +=(int x)//{{{

{

        int now=;

        if (topn==-)topn=;

        numb[now]+=x;

        while (numb[now]>=number::max_val)

        {

                numb[now+]+=numb[now]/number::max_val;

                numb[now]%=number::max_val;

                now++;

                if (now>topn)topn=now;

        }

}//}}}

void operator *=(int x)//{{{

{

        int i;

        for (i=;i<=topn;i++)

        {

                numb[i]*=x;

        }

        for (i=;i<=topn;i++)

        {

                if (numb[i]>=number::max_val)

                {

                        numb[i+]+=numb[i]/number::max_val;

                        numb[i]%=number::max_val;

                }

        }

        while (numb[topn+])

        {

                topn++;

                numb[topn+]+=numb[topn]/number::max_val;

                numb[topn]%=number::max_val;

        }

}//}}}

void operator -=(number &num)//{{{

{

        if (*this<num)throw "Error!\n->void operator -=(number &num)\n";

        int i;

        for (i=;i<=topn;i++)

        {

                numb[i]-=num.numb[i];

        }

        for (i=;i<=topn;i++)

        {

                while (numb[i]<)

                {

                        numb[i]+=number::max_val;

                        numb[i+]--;

                }

        }

        while (topn&&!numb[topn])topn--;

}//}}}

void operator --(int)//{{{

{

        if (topn==&&numb[]==)throw "Error!\n->void operator --(int)\n";

        int now=;

        numb[now]--;

        while (numb[now]<)

        {

                numb[now+]--;

                numb[now]+=number::max_val;

        }

        while (topn&&!numb[topn])topn--;

}//}}}

private:

int numb[max_len];

int topn;

void clear()

{

        topn=;

        memset(numb,,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>=;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>=;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=;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-;i>=;i--)

        {

                //压六位时

                //if (num.numb[i]<100000)out<<"0";

                //if (num.numb[i]<10000)out<<"0";

                if (num.numb[i]<)out<<"";

                if (num.numb[i]<)out<<"";

                if (num.numb[i]<)out<<"";

                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()-,num.topn=;i>=;i-=,num.topn++)

        {

                if (i-<(int)str.length())

                {

                        num.numb[num.topn]=(str[i]-'')+*(str[i-]-'')+*(str[i-]-'')+*(str[i-]-'');

                }else

                {

                        if (i-<(int)str.length())num.numb[num.topn]+=*(str[i-]-'');

                        if (i-<(int)str.length())num.numb[num.topn]+=*(str[i-]-'');

                        if (i<(int)str.length())num.numb[num.topn]+=(str[i]-'');

                }

        }

        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=;i<=num1.topn;i++)

                for (int j=;j<=num2.topn;j++)

                {

                        ret.numb[i+j]+=num1.numb[i]*num2.numb[j];

                        ret.numb[i+j+]+=ret.numb[i+j]/number::max_val;

                        ret.numb[i+j]%=number::max_val;

                }

        for (int i=;i<=ret.topn;i++)

        {

                ret.numb[i+]+=ret.numb[i]/number::max_val;

                ret.numb[i]%=number::max_val;

        }

        while (ret.numb[ret.topn+])

        {

                ret.topn++;

                ret.numb[ret.topn+]+=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][][];

int n,m;

number search_m(int now,int fl,int bo)

{

        int x,y;

        x=now-;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=;

        if (!fl)

        {

                if (num[y])

                {

                        //

                        if (num[x]==)

                                res+=search_m(now+,false,bo);//

                        else

                                res+=search_m(now+,false,true);//

                        if (now>)//首位非0

                        {

                                if (num[x]==)

                                        res+=search_m(now+,true,false);//

                                else

                                        res+=search_m(now+,true,bo);//

                        }

                }else if (!num[y])

                {

                        if (now>)//特殊处理m==0情况

                        {

                                if (num[x]==)

                                        res+=search_m(now+,false,false);//

                                else

                                        res+=search_m(now+,false,bo);//

                        }

                }

        }else

        {

                res+=search_m(now+,true,true);//

                res+=search_m(now+,true,true);//

        }

        return res;

}

int main()

{

        //freopen("input.txt","r",stdin);

        scanf("%s\n",str);

        int i,j,x,y;

        n=strlen(str);

        x=y=-;

        for (i=n-;i>=;i-=)

        {

                x++;

                for (j=max(,i-);j<=i;j++)

                        num0[x]=num0[x]*+str[j]-'';

        }

        n=x+;

        x=;

        while (~n)

        {

                num[x++]=num0[]%;

                for (i=n-;i>=;i--)

                {

                        if (i)num0[i-]+=(num0[i]&)*;

                        num0[i]/=;

                }

                while (n>= && !num0[n-])n--;

        }

        n=x;

        /*for (i=n-1;i>=0;i--)

          {

          printf("%d",num[i]);

          }

          printf("\n");*/

        /*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(,false,false);

        number xx;

        for (i=;i<n;i++)

        {

                xx=;

                xx=xx.pow((i-)/);

                ans+=xx;

        }

        cout<<ans<<endl;

        return ;

}

bzoj 1223: [HNOI2002]Kathy函数数位DP 高精度的更多相关文章

【SPOJ 2319】 BIGSEQ - Sequence （数位DP+高精度）
BIGSEQ - Sequence You are given the sequence of all K-digit binary numbers: 0, 1,..., 2K-1. You need ...
BZOJ&period;4513&period;[SDOI2016]储能表(数位DP)
BZOJ 洛谷切了一道简单的数位DP,终于有些没白做题的感觉了...(然而mjt更强没做过这类的题也切了orz) 看部分分,如果\(k=0\),就是求\(\sum_{i=0}^n\sum_{j=0} ...
[bzoj 1026]windy数（数位DP）
题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1026 分析: 简单的数位DP啦 f[i][j]表示数字有i位,最高位的数值为j的windy数总 ...
bzoj 1026 [SCOI2009]windy数数位dp
1026: [SCOI2009]windy数 Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline ...
bzoj 3131 [Sdoi2013]淘金（数位DP+优先队列）
Description 小Z在玩一个叫做<淘金者>的游戏.游戏的世界是一个二维坐标.X轴.Y轴坐标范围均为1..N.初始的时候,所有的整数坐标点上均有一块金子,共N*N块. 一阵风吹 ...
BZOJ 4513&colon; [Sdoi2016]储能表 [数位DP ！]
4513: [Sdoi2016]储能表题意:求\[ \sum_{i=0}^{n-1}\sum_{j=0}^{m-1} max((i\oplus j)-k,0) \] 写出来好开心啊...虽然思路不完 ...
BZOJ 4521 CQOI 2016 手机号码数位DP
4521: [Cqoi2016]手机号码 Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 539 Solved: 325[Submit][Status ...
BZOJ 2425 [HAOI2010]计数：数位dp + 组合数
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2425 题意: 给你一个数字n,长度不超过50. 你可以将这个数字: (1)去掉若干个0 ( ...
bzoj 3131 [Sdoi2013]淘金（数位dp）
题目描述小Z在玩一个叫做<淘金者>的游戏.游戏的世界是一个二维坐标.X轴.Y轴坐标范围均为1..N.初始的时候,所有的整数坐标点上均有一块金子,共N*N块. 一阵风吹过,金子的位置发生了 ...

随机推荐

【转载】移动web开发经验总结
本文出自: http://blog.163.com/hsb001_mobile/blog/static/15524028020111177221254/ 1.-webkit-tap-highlight ...
eclipse 和 android studio 编译时报 Unsupported major&period;minor version 52&period;0错解决办法
version 52.0 是java8的环境.当gradle tools 升级到2.2.1时候,可能编译时候会报该错误. 很多网友说更改java version,但是很多时候无效.下面是我遇到时候的解 ...
ios 缓存相关信息收集
链接:http://www.cnblogs.com/pengyingh/category/353093.html 使用NSURLCache让本地数据来代替远程UIWebView请求摘要: 原文作者: ...
Python3 字符编码
编码字符串是一种数据类型,但是,字符串比较特殊的是还有一个编码问题. 因为计算机只能处理数字,如果要处理文本,就必须先把文本转换为数字才能处理.最早的计算机在设计时采用8个比特(bit)作为一个字节 ...
Centos7安装Docker 基于Dockerfile 搭建httpd运行环境
Centos7安装Docker 基于Dockerfile 搭建httpd运行环境 docker docker搭建 docker build 本文档完成目标内容如下使用Docker搭建http服务器一 ...
&num; ？ &amp&semi; 号在url中的的作用
1. # 10年9月,twitter改版.一个显著变化,就是URL加入了"#!"符号.比如,改版前的用户主页网址为http://twitter.com/username改版后,就变 ...
linux 修改图片的尺寸
# convert -sample 50.png .png #把512*512的图片修改为500*500的图片 # which convert /usr/bin/convert # rpm -qf / ...
万能poi导入功能模板
同时支持2007版本和2003版本,空行过滤,纯数字类型数据格式处理,日期格式处理等 package com.yss.db.util; import com.yss.base.common.excep ...
【Java并发编程】14、Thread，线程说明
线程的状态:New.Runnable.Blocked.Waiting.Timed waiting.Terminated 1. RUNNABLE,对应"就绪"和"运行&qu ...
template&period;js简单入门
template.js是一款开源的JavaScript模板引擎,用来渲染页面的. github地址 https://github.com/yanhaijing/template.js 下载templa ...

bzoj 1223: [HNOI2002]Kathy函数 数位DP 高精度

1223: [HNOI2002]Kathy函数

Description

Input

Output

Sample Input

Sample Output

bzoj 1223: [HNOI2002]Kathy函数 数位DP 高精度的更多相关文章

随机推荐

相关文章

bzoj 1223: [HNOI2002]Kathy函数数位DP 高精度

bzoj 1223: [HNOI2002]Kathy函数数位DP 高精度的更多相关文章