1111: [POI2007]四进制的天平Wag

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 302  Solved: 201
[Submit][Status][Discuss]

Description

Mary准备举办一个聚会,她准备邀请很多的人参加她的聚会。并且她准备给每位来宾准备一些金子作为礼物。为了不伤及每个人的脸面,每个人获得的金子必须相同。Mary将要用一个天平来称量出金子。她有很多的砝码,所有砝码的质量都是4的幂。Mary将金子置于左边并且将砝码置于右盘或者两个盘。她希望每次称量都使用最少的砝码。并且,他希望,每次都用不同的称量方法称出相同质量的金子。对于给定的质量n,Mary希望知道最少需要用多少个砝码可以完成称量,并且想知道用这么多个砝码一共有多少种方式进行称量。

Input

输入文件仅包含一个整数,表示Mary希望给每个人的金子的质量。(1<=n<=10^1000)

Output

输出文件仅包含一个整数,表示一共可能的称量方式对10^9的模。

Sample Input

166

Sample Output

3
样例解释
一共有三种方式称量出166。166=64+64+16+16+4+1+1。166=256-64-16-16+4+1+1。166=256-64-16-4-4-1-1。
 
 
题解:%%claris
 

首先将n转化为四进制,从低位到高位DP

f[i]表示这一位不向下一位借位

g[i]表示这一位向下一位借位,但借的那个不算在i

f[0]=0,g[0]=inf

f[i]=merge(f[i-1]+b[i],g[i-1]+b[i]+1)

g[i]=merge(f[i-1]+4-b[i],g[i-1]+3-b[i])

 #include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<iostream> #define ll long long
#define mod 1000000000
#define N 2000 #define Wb putchar(' ')
#define We putchar('\n')
#define rg register int
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
}
inline void write(ll x)
{
if(x<) putchar('-'),x=-x;
if (x==) putchar();
int num=;char c[];
while(x) c[++num]=(x%)+,x/=;
while(num) putchar(c[num--]);
} int n;
int a[N],b[N];
char s[N];
struct Node
{
int x,y;
Node(){}
Node(int _x,int _y){x=_x,y=_y;}
friend Node operator+(Node x,int a){return Node(x.x+a,x.y);}
friend Node operator+(Node x,Node y)
{
return x.x==y.x?Node(x.x,(x.y+y.y)%mod):(x.x<y.x?x:y);
}
}f[N],g[N]; int main()
{
scanf("%s",s);int len=strlen(s);
for (int i=;i<=len;i++)
a[i]=s[len-i]-'';
while(len)
{
a[]=;
for (rg i=len;i>=;i--)
a[i-]+=(a[i]&)*,a[i]>>=;
for (b[++n]=a[]/;len&&!a[len];len--);
}
f[]=Node(,),g[]=Node(N,),n++;
for (rg i=;i<=n;i++)
f[i]=(f[i-]+b[i])+(g[i-]+(b[i]+)),
g[i]=(f[i-]+(-b[i]))+(g[i-]+(-b[i]));
write(f[n].y);
}
05-11 11:07