题解 P2609 【[ZJOI2012]数列】

· · 题解

先来看一下 a_n：a_n=1 \times a_n+0 \times a_{n+1}

若 n 为偶数：

1 \times a_n+0 \times a_{n+1}=1 \times a_{\frac{n}{2}}+0 \times a_{\frac{n}{2}}+0 \times a_{\frac{n}{2}+1}=(1+0) \times a_{\frac{n}{2}}+0 \times a_{\frac{n}{2}+1}

否则（n 为奇数）：

1 \times a_n+0 \times a_{n+1}=1 \times a_{\lfloor \frac{n}{2} \rfloor}+1 \times a_{\lfloor \frac{n}{2} \rfloor+1}+0 \times a_{\lfloor \frac{n}{2} \rfloor+1}=1 \times a_{\lfloor \frac{n}{2} \rfloor}+(1+0) \times a_{\lfloor \frac{n}{2} \rfloor+1}

那么继续求出 n/2 即可。

这只是对于第一个数，对于之后的任意数有：

若 n 为偶数：

l \times a_n+r \times a_{n+1}=l \times a_{\frac{n}{2}}+r \times a_{\frac{n}{2}}+r \times a_{\frac{n}{2}+1}=(l+r) \times a_{\frac{n}{2}}+r \times a_{\frac{n}{2}+1}

之后 l=l+r,r 不变，n=n/2

否则（n 为奇数）：

l \times a_n+r \times a_{n+1}=l \times a_{\lfloor \frac{n}{2} \rfloor}+l \times a_{\lfloor \frac{n}{2} \rfloor+1}+r \times a_{\lfloor \frac{n}{2} \rfloor+1}=l \times a_{\lfloor \frac{n}{2} \rfloor}+(l+r) \times a_{\lfloor \frac{n}{2} \rfloor+1}

之后 l 不变，r=l+r，n=\lfloor \frac{n}{2} \rfloor

最后当 n=0 时输出 r，因为最后的式子是：l \times a_0+r \times a_1，而 a_0=0,a_1=1。

还不懂？举个例子，求出 a_{10}：

a_{10} =1 \times a_{10}+0 \times a_{11}=1 \times a_{\frac{10}{2}}+0 \times a_{\frac{10}{2}}+0 \times a_{\frac{10}{2}+1} =(1+0) \times a_5+0 \times a_6=1 \times a_{\lfloor \frac{5}{2} \rfloor}+1 \times a_{\lfloor \frac{5}{2} \rfloor+1}+0 \times a_{\lfloor \frac{5}{2} \rfloor+1} =1 \times a_2+(1+0) \times a_3=1 \times a_{\frac{2}{2}}+1 \times a_{\frac{2}{2}}+1 \times a_{\frac{2}{2}+1} =(1+1) \times a_1+1 \times a_2=2 \times a_{\lfloor \frac{1}{2} \rfloor}+2 \times a_{\lfloor \frac{1}{2} \rfloor+1}+1 \times a_{\lfloor \frac{1}{2} \rfloor+1} =2 \times a_0+(2+1) \times a_1=2 \times 0+3 \times 1=3

所以答案就是这样：

long long a=1,b=0; // 把文中的 l,r 改成 a,b 了
while(n)
{
    if(n%2==0) a=a+b; // (!(n&1)) a=a+b;
    else b=a+b;
    n/=2; // n>>=1; 
}
cout<<b;

一个代码。

但是 n \le 10^{100}

所以这样写只能得50 分

于是这题要写高精度——

在此，我想发一篇较为清爽、整齐的高精度代码。

#include<bits/stdc++.h>
using namespace std;

char n[110];
int n1[110],a[110],b[110],c[110];

int main()
{
    int t;
    cin>>t;
    for(; t; --t)
    {
        memset(a,0,sizeof(a)); // 每个测试数据都要清零
        memset(b,0,sizeof(b));
        cin>>n;
        a[0]=1,b[0]=0; // 赋值
        int l=strlen(n),l1=1,l2=0; // l是n的长度，l1是a的长度，l2是b的长度

        if(l==1 && n[0]==0)
        { // 特判==0的情况
            cout<<0<<endl;
            continue;
        }

        for(int i=0; i<l; ++i)  n1[l-i-1]=n[i]-'0'; // 逆序储存
        while(l)
        { // 当长度不为0，就是50分代码中的 while(n)
            memset(c,0,sizeof(c)); // c数组为a+b的值，先清零
            int l3=max(l1,l2); // 以下是高精加
            for(int i=0; i<l3; ++i)
            {
                c[i]+=a[i]+b[i];
                c[i+1]+=c[i]/10; // 加进位
                c[i]%=10;
            }
            if(c[l3]) ++l3; // 如果相加之后最高位有进位，长度++

            if(n1[0]%2==0)
            { // a=a+b;
                for(int i=0; i<l3; ++i) a[i]=c[i]; // 赋值
                l1=l3; // 长度更新
            } else { // b=a+b;
                for(int i=0; i<l3; ++i) b[i]=c[i]; // 同上
                l2=l3;
            }

            int yushu=0; // 上一个除以2留下的余数
            for(int i=l-1; i>=0; --i)
            { // 除以2
                int k=(yushu*10+n1[i])/2; // 当前位置除以2后是多少，要注意加上上一个剩的余数
                yushu=n1[i]%2; // 更新余数
                n1[i]=k; // 更新这个数
            }
            if(l>0 && !n1[l-1]) --l; // 如果除以二后高位变成0了，长度要减，即“去掉前导0”
        }
        for(int i=l2-1; i>=0; --i) cout<<b[i]; // 最后输出b
        cout<<endl;
    }
    return 0;
}

于是，这道紫题就 AC 啦！

这是本蒟蒻的第二篇题解，如有疑问，欢迎各位大佬在下方留言！

update 4.5 更新代码风格。

update 8.6 被莫名其妙撤下该题解后改了一些小问题，又更新了代码风格，交上去。