震惊！$O(n\log^2 n)$算法竟被$O(n^2)$吊打

NaCly_Fish @ 2019-01-13 10:45:01

by NaCly_Fish @ 2019-01-13 10:45:11

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define N 10003
#define pi 3.141592653589793
using namespace std;

struct BigInt{
    int num[N];
    int size;
    bool negative;
    bool operator < (const BigInt& a) const{
        if(a.negative&&!negative) return false;
        if(negative&&!a.negative) return true;
        bool f = negative;
        for(int i=size;i>=1;--i){
            if(a.num[i]==num[i]) continue;
            if(f) return num[i]>a.num[i];
            else return num[i]<a.num[i];
        }
        return false;
    }
    bool operator > (const BigInt& a) const{
        if(a.negative&&!negative) return true;
        if(negative&&!a.negative) return false;
        bool f = negative;
        for(int i=size;i>=1;--i){
            if(a.num[i]==num[i]) continue;
            if(!f) return num[i]>a.num[i];
            else return num[i]<a.num[i];
        }
        return false;
    }
    bool operator == (const BigInt& a) const{
        if(negative!=a.negative) return false;
        if(size!=a.size) return false;
        for(int i=size;i>=1;--i)
            if(num[i]!=a.num[i]) return false;
        return true;    
    }
};

struct complex{
    double r,i;
    complex(double r=0,double i=0):r(r),i(i){}
    complex operator + (const complex& a) const{
        return complex(r+a.r,i+a.i);
    }
    complex operator * (const complex& a) const{
        return complex(r*a.r-i*a.i,r*a.i+i*a.r);
    }
    complex operator - (const complex& a) const{
        return complex(r-a.r,i-a.i);
    }
};

int rev_[N];
complex F[N],G[N];

void FFT(complex *a,int type,int lim){
    for(int i=0;i<lim;++i){
        if(i>=rev_[i]) continue;
        swap(a[i],a[rev_[i]]);
    }
    for(int mid=1;mid<lim;mid<<=1){
        complex rt = complex(cos(pi/mid),type*sin(pi/mid));
        int r = mid<<1;
        for(int j=0;j<lim;j+=r){
            complex w = complex(1,0);
            for(int k=0;k<mid;++k){
                complex x = a[j+k];
                complex y = w*a[j+k+mid];
                a[j+k] = x+y;
                a[j+k+mid] = x-y;
                w = w*rt;
            }
        }
    }
}

inline BigInt newBigInt(string n){
    int t = 0;
    BigInt a;
    memset(a.num,0,sizeof(a.num));
    a.size = n.length();
    if(n[0]=='-'){
        t = 1;
        a.size--;
    }
    for(int i=1;i<=a.size;++i)
        a.num[i] = n[a.size-i+t]-'0';
    a.negative = (t==0)?false:true; 
    return a;   
}

inline BigInt toBigInt(int a){
    BigInt b = newBigInt("0");
    int l = 1;
    if(a<0){
        a = -a;
        b.negative = true;
    }
    while(a){
        b.num[l] = a%10;
        a /= 10;
        ++l;
    }
    b.size = l-1;
    return b;
}

const BigInt ZERO = newBigInt("0");
const BigInt ONE = newBigInt("1");
const BigInt TWO = newBigInt("2");
const BigInt TEN = newBigInt("10");

void print(BigInt a){
    int l = a.size;
    if(a.negative) putchar('-');
    for(int i=l;i>=1;--i)
        putchar(a.num[i]+'0');
}

BigInt add(BigInt a,BigInt b);
BigInt subtract(BigInt a,BigInt b);

BigInt multiply(BigInt a,BigInt b){
    int l,n,m,lim,cnt;
    if(a==ZERO||b==ZERO) return ZERO;
    BigInt c = ZERO;
    cnt = l = 0; 
    lim = 1;
    n = a.size-1;
    m = b.size-1;
    memset(F,0,sizeof(F));
    memset(G,0,sizeof(G));
    for(int i=0;i<=n;++i) F[i].r = a.num[i+1];
    for(int i=0;i<=m;++i) G[i].r = b.num[i+1];
    cnt = n+m;
    while(lim<=cnt){
        lim <<= 1;
        ++l;
    } 
    for(int i=0;i<lim;++i)
        rev_[i] = (rev_[i>>1]>>1)|((i&1)<<(l-1));
    FFT(F,1,lim);
    FFT(G,1,lim);    
    for(int i=0;i<=lim;++i)
        F[i] = F[i]*G[i];
    FFT(F,-1,lim);
    for(int i=0;i<=cnt;++i)
        c.num[i+1] = F[i].r/lim+0.5;    
    ++cnt;    
    for(int i=1;i<=cnt;++i){
        if(c.num[i]<10) continue;
        c.num[i+1] += c.num[i]/10;
        c.num[i] %= 10;
    }
    while(c.num[cnt+1]>0) ++cnt;
    int i = cnt;
    while(c.num[i]==0) --i;
    c.size = i;    
    c.negative = a.negative^b.negative;
    return c;
}

BigInt add(BigInt a,BigInt b){
    BigInt c = ZERO;
    if(a.negative&&b.negative){
        a.negative = false;
        b.negative = false;
        c = add(a,b);
        c.negative = true;
        return c;
    }else if(a.negative&&!b.negative){
        a.negative = false;
        c = subtract(b,a);
        return c;
    }else if(!a.negative&&b.negative){
        b.negative = false;
        c = subtract(a,b);
        return c;
    }
    int l = max(a.size,b.size);
    for(int i=1;i<=l;++i)
        c.num[i] = a.num[i]+b.num[i];
    for(int i=1;i<=l;++i){
        if(c.num[i]<10) continue;
        c.num[i+1]++;
        c.num[i] -= 10;
    }
    c.size = l;
    if(c.num[l+1]!=0) c.size++;
    return c;
}

BigInt _divide(BigInt a,int b){
    bool flag = false;
    if(b<0){
        flag = true;
        b = -b;
    }
    BigInt c = ZERO;
    if(a<toBigInt(b)) return c;
    int l,n = a.size;
    l = n;
    while(a.num[n]<b&&l>=1){
        a.num[n-1] += (a.num[n]<<3)+(a.num[n]<<1);
        a.num[n] = 0;
        --n;
    }
    for(int i=n;i>=1;--i){
        if(a.num[i]>=b){
            c.num[i] = a.num[i]/b;
            a.num[i] %= b;
        }
        a.num[i-1] += (a.num[i]<<3)+(a.num[i]<<1);
    }
    c.size = n;
    c.negative = a.negative^flag;
    return c;
}

BigInt subtract(BigInt a,BigInt b){
    BigInt c = ZERO;
    if(a.negative&&!b.negative){
        a.negative = false;
        c = add(a,b);
        c.negative = true;
        return c;
    }else if(a.negative&&b.negative){
        a.negative = false;
        b.negative = false;
        return subtract(b,a);
    }else if(!a.negative&&b.negative){
        b.negative = false;
        c = add(a,b);
        c.negative = false;
        return c;
    }
    if(a<b){
        c = subtract(b,a);
        c.negative = true;
        return c;
    }else if(a==b) return c;
    int l = max(a.size,b.size);
    for(int i=1;i<=l;++i)
        c.num[i] = a.num[i]-b.num[i];
    for(int i=1;i<=l;++i){
        if(c.num[i]>=0) continue;
        c.num[i] += 10;
        c.num[i+1]--;
    }
    while(!c.num[l]) --l;
    if(l==0) l = 1;
    c.size = l;
    return c;
}

BigInt power(BigInt a,int t){
    bool flag = false;
    BigInt b = ONE;
    if(t&1&&a.negative) flag = true; 
    while(t){
        if(t&1) b = multiply(a,b);
        a = multiply(a,a);
        t >>= 1;
    }
    a.negative = flag;
    return b;
}

BigInt _mod(BigInt a,int b){
    BigInt c = _divide(a,b);
    c = multiply(toBigInt(b),c);
    c = subtract(a,c);
    return c;
}

inline BigInt Abs(BigInt a){
    a.negative = false;
    return a;
}

struct grid{
    BigInt m[2][2];
};

inline void read(int &x){
    x = 0;
    char c = getchar();
    while(c<'0'||c>'9') c = getchar();
    while(c>='0'&&c<='9'){
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
}

inline grid mul(grid a,grid b){
    grid c;
    c.m[0][0] = add(multiply(a.m[0][0],b.m[0][0]),multiply(a.m[1][0],b.m[0][1]));
    c.m[1][0] = add(multiply(a.m[0][0],b.m[1][0]),multiply(a.m[1][0],b.m[1][1]));
    c.m[0][1] = add(multiply(a.m[0][1],b.m[0][0]),multiply(a.m[1][1],b.m[0][1]));
    c.m[1][1] = add(multiply(a.m[0][1],b.m[1][0]),multiply(a.m[1][1],b.m[1][1]));
    return c;
}

inline grid mpow(grid a,int t){
    grid ans;
    ans.m[0][0] = ZERO;
    ans.m[0][1] = ONE;
    ans.m[1][0] = ONE;
    ans.m[1][1] = ONE;
    while(t){
        if(t&1) ans = mul(ans,a);
        a = mul(a,a);
        t >>= 1;
    }
    return ans;
}

int main(){
    int n;
    read(n);
    if(n==0){
        putchar('0');
        return 0;
    }
    grid a;
    a.m[0][0] = ZERO;
    a.m[0][1] = ONE;
    a.m[1][0] = ONE;
    a.m[1][1] = ONE;
    grid ans = mpow(a,n-1);
    print(ans.m[1][1]);
    return 0;
}

by chen_zhe @ 2019-01-13 10:45:54

@NaCly_Fish 那么下次搞个n=10^5的版本吧（大雾）

另外这都是什么神仙啊

by ezoixx130 @ 2019-01-13 10:48:18

你要知道FFT的常数

by chen_zhe @ 2019-01-13 10:49:13

@ezoixx130 fft常数一般还行吧

by 花里心爱 @ 2019-01-13 10:55:37

反正Orz就对了
这都是什么神仙啊qwq

by 已注销%Jm9VScx @ 2019-01-13 10:56:01

我是卡常数大佬

by NaCly_Fish @ 2019-01-13 10:57:11

@Irressey orz您fAKe啊

by 花里心爱 @ 2019-01-13 10:58:10

@NaCly_Fish 窝连高精都不会dalao就开始用fft虐题了qwq

by Siyuan @ 2019-01-13 11:03:21

@NaCly_Fish Orz 用 \texttt{FFT} 虐普及题目的神仙！

by NaCly_Fish @ 2019-01-13 11:03:49

@Irressey 窝连A+B都不会dalao就开始吊打集训队了qwq