题解 P4461 【[CQOI2018]九连环】

题解 P4461 【[CQOI2018]九连环】

由于各位大佬已经用各种方法,将公式推得我这里便不再过多阐述,我们来谈谈本题的实现~

首先,我们先来看公式:$\lfloor\frac{2^{n+1}}{3}\rfloor$

我们知道,因为n<=1e5，所以$|2^{n+1}|$很小,而且询问也只有10,所以我们如果能较快求出$2^{n+1}$我们再跑个高精除低精便可以通过此题了...

于是现在问题转化到如何快速求$2^{n+1}$,于是,某大佬站出来刷刷刷...快速幂+FFT 对此我只能orzzzzz

由于我太弱,所以懒得打FFT了,但是打高精明显GG啊...这可怎么办呢？

其实,我们只需要稍加优化即可:我们可以使用低精乘法来代替部分的高精乘法,从而使得代码加速最后原地起飞！

不会低精优化高精的可以去这里学习看故事

下面给出代码:

//#pragma GCC optimize(3,"Ofast","inline")//手动O3优化
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
#include<bits/stdc++.h>
using namespace std;
const unsigned long long T=5e17;
inline string operator*(string x,unsigned long long y){//高精乘低精 
    int len=x.size();
    unsigned long long a[100000];
    for(int i=0;i<len;++i){
        a[i]=x[len-i-1]-'0';
        a[i]*=y;
    }
    for(int i=0;i<len;++i){
        if(a[i]>9){
            if(i==len-1){
                a[len++]=0;
            }
            a[i+1]+=a[i]/10;
            a[i]%=10;
        }
    }
    while(len&&!a[len-1]){
        len--;
    }
    string ans="";
    for(int i=len-1;~i;--i){
        ans+=a[i]+'0';
    }
    return ans;
}
inline string operator/(string x,int y){//高精除低精 
    int len=x.size(),yu=0;
    bool flag=0;
    string res="";
    for(int i=0;i<len;++i){
        yu=yu*10+x[i]-'0';
        if(flag){
            res+=yu/3+'0';
            yu%=3;
            continue;
        }
        if(yu>=3){
            flag=1;
            res+=yu/3+'0';
            yu%=3;
        }
    }
    return res;
}
inline string fksc(int x,int y){//低精乘法优化高精乘法 
    unsigned long long ji=1;
    string res="1";
    while(y--){
        ji*=x;
        if(ji<=T){
            continue; 
        }
        res=res*ji;
        ji=1;
    }
    res=res*ji;
    return res;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        string res=fksc(2,n+1);
        cout<<res/3<<endl;
    }
    return 0;
}

O(1)<<代码的复杂度=O(可过)<<O(nm|s|)

当然,为了追求较快速度,可以先输入询问,然后进行一次低精优化高精处理完所有情况,然后再回答~