《真·入门(233行代码)》求简化
查看原帖
《真·入门(233行代码)》求简化
1771991
FUNN楼主2025/6/27 11:06
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
namespace mikiwang{
    class complex{
        public:
            long double r,v;
            complex(long double r_=0){r=r_;v=0;}
            complex(long double r_,long double v_){r=r_;v=v_;}
            complex operator+(const complex &c)const{return complex(r+c.r,v+c.v);}
            complex &operator+=(const complex &c){return *this=*this+c;}
            complex operator-(const complex &c)const{return complex(r-c.r,v-c.v);}
            complex &operator-=(const complex &c){return *this=*this-c;}
            complex operator*(const complex &c)const{return complex(r*c.r-v*c.v,v*c.r+r*c.v);}
            complex &operator*=(const complex &c){return *this=*this*c;}
            complex operator/(const complex &c)const
            {long double d=c.r*c.r-c.v*c.r;return complex((r*c.r+v*c.v)/d,(r*c.v+v*c.r)/d);}
            complex operator/=(const complex &c){return *this=*this/c;}
            complex operator-()const{return complex(-r,-v);}
    };
}
namespace mikiwang{
    class polymerization{
        private:
            int len;
            complex*data;
            static void fft(complex*,int,int);
        public:
            polymerization(int=0);
            polymerization(const polymerization&);
            ~polymerization();
            int length()const;
            operator complex*();
            operator const complex*()const;
            polymerization &operator=(const polymerization&);
            polymerization &resize(int);
            polymerization operator-()const;
            polymerization operator+(const polymerization&)const;
            polymerization operator-(const polymerization&)const;
            polymerization operator*(long double)const;
            polymerization operator*(complex)const;
            polymerization operator/(long double)const;
            polymerization operator/(complex)const;
            polymerization operator*(const polymerization&)const;
            polymerization inverse()const;
            polymerization &reverse();
            polymerization operator/(const polymerization&)const;
            polymerization operator%(const polymerization&)const;
    };
}
using mikiwang::polymerization;
polymerization pow(polymerization a,long long n,const polymerization &p){
    polymerization ret;
    ret[0]=1;
    while(n){
        if(n&1)ret=ret*a%p;
        a=a*a%p;
        n>>=1;
    }
    return ret;
}
long double abs(long double x){
    if(x<0){
        return -x;
    }
    return x;
}
int main(){
    polymerization a(1),g(2),r;
    long long n;
    scanf("%lld",&n);
    if(!n){
        printf("0.00\n");
        return 0;
    }
    a[0]=0;
    a[1]=1;
    g[0]=1;
    g[1]=1;
    g[2]=-1;
    r=pow(a,n,g);
    printf("%.2Lf\n",abs(r[1].r));
    return 0;
}
namespace mikiwang{
    using std::max;
    using std::swap;
    polymerization::polymerization(int len_){
        len=len_;
        data=new complex[len+1];
        for(int i=0;i<=len;i++){
            data[i].r=0;
            data[i].v=0;
        }
    }
    polymerization::polymerization(const polymerization &a){
        len=-1;
        data=0;
        *this=a;
    }
    polymerization::~polymerization(){
        len=-1;
        delete data;
    }
    int polymerization::length()const{
        return len;
    }
    polymerization::operator complex*(){
        return data;
    }
    polymerization::operator const complex*()const{
        return data;
    }
    polymerization &polymerization::operator=(const polymerization &a){
        resize(a.len);
        for(int i=0;i<=len;i++)data[i]=a[i];
        return *this;
    }
    polymerization &polymerization::resize(int len_){
        if(len<len_){
            complex*p=new complex[len_+1];
            for(int i=0;i<=len;i++)p[i]=data[i];
            delete data;
            data=p;
        }
        len=len_;
        return *this;
    }
    polymerization polymerization::operator-()const{
        polymerization ret(*this);
        for(int i=0;i<=len;i++)ret[i]=-ret[i];
        return ret;
    }
    polymerization polymerization::operator+(const polymerization &a)const{
        polymerization ret=max(len,a.len);
        for(int i=0;i<=len;i++)ret[i]+=data[i];
        for(int i=0;i<=len;i++)ret[i]+=a[i];
        return ret;
    }
    polymerization polymerization::operator-(const polymerization &a)const{
        polymerization ret=max(len,a.len);
        for(int i=0;i<=len;i++)ret[i]+=data[i];
        for(int i=0;i<=len;i++)ret[i]-=a[i];
        return ret;
    }
    void polymerization::fft(complex *a,int n,int op){
        static const long double PI=acos(-1);
        int *pos=new int[n];
        pos[0]=0;
        for(int i=1;i<n;i++)pos[i]=(pos[i>>1]>>1)|((i&1)*(n>>1));
        for(int i=1;i<n;i++)if(i<pos[i])swap(a[i],a[pos[i]]);
        complex A,B;
        for(int l=1;l<n;l<<=1){
            for(int i=0;i<n;i+=l<<1){
                for(int j=0;j<l;j++){
                    A=a[i+j];
                    B=complex(cos(PI*j/l),op*sin(PI*j/l))*a[i+j+l];
                    a[i+j]=A+B;
                    a[i+j+l]=A-B;
                }
            }
        }
        delete pos;
    }
    polymerization polymerization::operator*(long double k)const{
        polymerization ret(*this);
        for(int i=0;i<=len;i++)ret[i]*=k;
        return ret;
    }
    polymerization polymerization::operator*(complex c)const{
        polymerization ret(*this);
        for(int i=0;i<=len;i++)ret[i]*=c;
        return ret;
    }
    polymerization polymerization::operator/(long double k)const{
        polymerization ret(*this);
        for(int i=0;i<=len;i++)ret[i]/=k;
        return ret;
    }
    polymerization polymerization::operator/(complex c)const{
        polymerization ret(*this);
        for(int i=0;i<=len;i++)ret[i]/=c;
        return ret;
    }
    polymerization polymerization::operator*(const polymerization &a_)const{
        complex *a,*b;
        polymerization ret(len+a_.len);
        int l=1;
        while(l<=ret.len)l<<=1;
        a=new complex[l];b=new complex[l];
        for(int i=0;i<=len;i++)a[i]=data[i];
        for(int i=0;i<=a_.len;i++)b[i]=a_[i];
        fft(a,l,1);fft(b,l,1);
        for(int i=0;i<l;i++)a[i]*=b[i];
        fft(a,l,-1);
        for(int i=0;i<=ret.len;i++)ret[i]=a[i]/l;
        delete a;delete b;
        return ret;
    }
    polymerization polymerization::inverse()const{
        polymerization g(1),g1;
        g[0]=1;
        g[0]/=data[0];
        g[1]=-g[0]*g[0]*data[1];
        while(g.len<=len){
            g1=g*g;
            g=g*2-(*this*g1).resize(g.len<<1);
        }
        return g.resize(len);
    }
    polymerization &polymerization::reverse(){
        std::reverse(data,data+len+1);
        return *this;
    }
    polymerization polymerization::operator/(const polymerization &a)const{
        if(len<a.len)return *this;
        polymerization k,ra(*this),rb(a);
        ra.reverse().resize(len-a.len);
        rb.reverse().resize(len-a.len);
        k=ra*rb.inverse();
        return k.resize(len-a.len).reverse();
    }
    polymerization polymerization::operator%(const polymerization &a)const{
        if(len<a.len)return *this;
        if(!a.len){
            polymerization ret(0);
            ret[0]=data[0]/a[0];
            return ret;
        }
        return (*this-*this/a*a).resize(a.len-1);
    }
}
2025/6/27 11:06
加载中...