BZOJ 1265: [AHOI2006]斐波卡契的兔子

卡卡开始养兔子了！妈妈给他买了一对刚出生的兔子，卡卡了解到兔子的繁殖规律是这样的：才出生的一对兔子在一个月后将第一次生出一胎 a 对兔子，接着在出生后的二个月又将生出 b 对兔子，在第三个月和以后每个月都会繁殖 c 对兔子。(a <= b <= c) 由斐波纳契数列我们知道兔子的繁殖速度是很快的，然而卡卡有兔子一样多的好朋友，卡卡想在 m 个月后有 k 对兔子，以便分给他们的好友，他的愿望是否能够实现呢？
[任务] 编写一个程序：从输入文件中读入输入信息；计算 m 个月后卡卡将有多少对兔子，设之为 P；计算如果 m 个月后卡卡要拥有至少 k 对兔子，那么开始时妈妈至少应该为卡卡购买多少对兔子，设之为 Q；将结果输出至输出文件。

Input

输入文件的第一行有 4 个正整数：a, b, c 和 m；而第二行则仅含一个正整数 k。它们的含义见上文描述。

Output

你的程序将向输出文件输出两行，第一行是一个整数 P 而第二行是一个整数 Q。

Sample Input

0 1 1 10
10000

Sample Output

89
113

HINT

0 <= a <= b <= c <= 100, 1 <= m <= 3 000, 1 <= k <= 10^6000

Solution

我们用 $x,y,z$ 表示一个月、两个月、三个月及以上的兔子，那么每次 $x=ax+by+cz,y=x,z=y+z$ 就可以求出 $p$，而 $q$ 就是 $\frac k p$ 向上取整。
$\frac k p$ 可以用 $p,2p,4p,...,(2^t)p$ 去求。
然而为什么 AC 的人这么少呢。。

Code

#include<bits/stdc++.h>

#define gm 1000
#define cas 10000000
#define max2 20050

int a[gm],b[gm],c[gm],k[gm],m,al,bl,cl,kl,t[gm],aa,bb,cc,r1[gm],r2[gm],r3[gm],l1,l2,l3;
int f[max2][gm],fl[max2],tf[max2][gm],tfl[max2],ans[gm],ansl,rrt[gm];
char tmp[10000];

inline void print(int *x,int xl)
{
    printf("%d",x[xl-1]);
    for(int i=xl-2;i>=0;i--)printf("%07d",x[i]);
}

inline int max(int a,int b)
{
    if(a>b)return a;else return b;
}

inline void add(int *x,int *y,int &xl,int yl)
{
    int ll=max(xl,yl);
    for(int i=0;i<ll;i++)
    {
        x[i]+=y[i];
        if(x[i]>=cas)x[i]-=cas,x[i+1]++;
    }
    if(x[ll])xl=ll+1;else xl=ll;
}

inline void addto(int *x,int *y,int *z,int xl,int yl,int &zl)
{
    zl=max(xl,yl);
    z[0]=0;
    for(int i=0;i<zl;i++)
    {
        z[i]+=x[i]+y[i];
        if(z[i]>=cas)z[i]-=cas,z[i+1]=1;else z[i+1]=0;
    }
    if(z[zl])zl++;
}

inline void multo(int *x,int y,int *z,int xl,int &zl)
{
    z[0]=0;
    for(int i=0;i<xl;i++)
    {
        z[i]+=x[i]*y;
        z[i+1]=z[i]/cas;
        z[i]%=cas;
    }
    if(z[xl])zl=xl+1;else zl=xl;
}

inline bool larger(int *x,int *y,int xl,int yl)
{
    if(xl>yl)return true;
    if(xl<yl)return false;
    for(int i=max(xl,yl)-1;i>=0;i--)
    {
        if(x[i]>y[i])return true;
        if(x[i]<y[i])return false;
    }
    return false;
}

inline void dec(int *x,int *y,int &xl,int yl)
{
    for(int i=0;i<xl;i++)
    {
        x[i]-=y[i];
        while(x[i]<0)x[i]+=cas,x[i+1]--;
    }
    while(xl&&!x[xl-1])xl--;
}

int main()
{
    al=1,bl=0,cl=0;
    a[0]=1;
    scanf("%d%d%d%d",&aa,&bb,&cc,&m);
    scanf("%s",tmp);
    int tml=strlen(tmp),tmp2=1;
    std::reverse(tmp,tmp+tml);
    kl=(tml+6)/7;
    for(int i=0;i<tml;i++)
    {
        if(i%7==0)tmp2=1;
        k[i/7]=k[i/7]+(tmp[i]-'0')*tmp2;
        tmp2*=10;
    }
    for(int i=0;i<m;i++)
    {
        multo(a,aa,r1,al,l1);
        multo(b,bb,r2,bl,l2);
        multo(c,cc,r3,cl,l3);
        add(c,b,cl,bl);
        memcpy(b,a,al*4);
        bl=al;
        addto(r1,r2,a,l1,l2,al);
        add(a,r3,al,l3);
    }
    add(a,b,al,bl);
    add(a,c,al,cl);
    print(a,al);
    printf("\n");
    memcpy(f[0],a,al*4);
    fl[0]=al;
    tf[0][0]=1;
    tfl[0]=1;
    ansl=0;
    int ma;
    for(ma=0;!larger(f[ma],k,fl[ma],kl);ma++)
    {
        multo(f[ma],2,f[ma+1],fl[ma],fl[ma+1]);
        multo(tf[ma],2,tf[ma+1],tfl[ma],tfl[ma+1]);
    }
    for(int i=ma-1;i>=0;i--)
    {
        if(!larger(f[i],k,fl[i],kl))
        {
            dec(k,f[i],kl,fl[i]);
            add(ans,tf[i],ansl,tfl[i]);
        }
    }
    if(kl)
    {
        rrt[0]=1;
        add(ans,rrt,ansl,1);
    }
    print(ans,ansl);
    printf("\n");
    return 0;
}

日期： 2016-09-13

标签： BZOJ 高精度

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/24/ 查看。