
 7通过
 17提交
 题目提供者 洛谷
 评测方式 云端评测
 标签 动态规划,动规,dp 进制 POI 2007 高性能
 难度 提高+/省选
 时空限制 1000ms / 128MB
最新讨论 显示
题目描述
Byteasar the dragon intends to throw a party, to which he would like to invite many guests. Byteasar wouldalso like to present each guest with an amount of gold to honour the party. Each should receive the sameamount, so that no one's pride is hurt. The dragon is going to weigh out gold for subsequent guests with abeam balance. He has different types of standard masses at his disposal, each type weighing a certain powerof four. Conveniently, Byteasar has lots of the standard masses, hence he may use any number of masses ofany type (power of four) he finds appropriate. Byteasar will always lay the gold on the left weighing basinand the masses on the right or both weighing basins. The dragon wishes to use the least number of massespossible for each weighing. Furthermore, to entertain his guests, Byteasar would like to measure out the goldin unique manner for each person (ie. using different masses or distributing them among the weighing basinsin a different way).
Since dragons' lack of arithmetic skills is legendary, Byteasar has aksed you to write a programme thatwill determine how many guests he may invite, that is, finds the maximum number of ways in which $n$ grammes of gold can be weighed out using the minimum number of masses possible. Should you fare well,you will also get your share!
TaskWrite a programme that:
reads from the standard input the amount of gold (in grammes) which Byteasar intends to present each guest with, calculates the number of ways in which this amount of gold can be weighed out using the minimum number of masses possible, writes out the remainder of dividing the result by $10^9$ to the standard output.
给定一个数n，要求将n表示成一些4^k的数之和/差的形式，要求用的数最少，求方案数
输入输出格式
输入格式：In the first and only line of the standard input there is one positive integer $n$($1\le n<10^{1000}$).
It is the amountof gold (in grammes) which Byteasar intends to present each guest with.
输出格式：One integer should be written out to the standard output the remainder of dividing by $10^9$ the maximumnumber of guests Byteasar can invite (that is, the maximum number of ways in which $n$ grammes of gold canbe weighed out using the minimum number of masses possible).