代码大全

常数优化

编译器卡常优化（CF上比较有用）

#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

读入优化：

inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}

mmap读入优化：

#include
    
     #include
     
      class MMapInput {    private:        char *buf,*p;        int size;    public:        MMapInput() {            register int fd=fileno(stdin);            struct stat sb;            fstat(fd,&sb);            size=sb.st_size;            buf=reinterpret_cast
      
       (mmap(0,size,PROT_READ,MAP_PRIVATE,fileno(stdin),0));            p=buf;        }        char getchar() {            return (p==buf+size||*p==EOF)?EOF:*p++;        }};MMapInput mmi;inline int getint() {    register char ch;    while(!isdigit(ch=mmi.getchar()));    register int x=ch^'0';    while(isdigit(ch=mmi.getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}
      
     
    

数论

扩欧求逆元：

void exgcd(const int &a,const int &b,int &x,int &y) {    if(!b) {        x=1,y=0;        return;    }    exgcd(b,a%b,y,x);    y-=a/b*x;}inline int inv(const int &x) {    int ret,tmp;    exgcd(x,mod,ret,tmp);    return (ret%mod+mod)%mod;}

多项式

FFT

inline void init_ru(const int &n) {    for(register int i=0;i
    
     j) std::swap(f[i],f[j]);        for(register int l=n>>1;(j^=l)
     
      >=1);    }    for(register int i=2;i<=n;i<<=1) {        const int m=i>>1;        for(register int j=0;j
     
    

FWT异或：

inline void fwt(int a[]) {    for(register int j=0;j
    
     >j&1) continue;            const int x=a[i],y=a[(1<
    

字符串

后缀数组求sa[i]和rank[i]：

inline bool cmp(const int &i,const int &j) {    if(rank[i]!=rank[j]) return rank[i]

后缀数组求lcp[i]：

inline void init_lcp() {    for(register int i=0,h=0;i
    
     0) h--;        const int j=sa[rank[i]-1];        while(j+h
     
    

计算几何：

自适应辛普森法：

inline double simpson(const double &a,const double &b) {    const double c=(a+b)/2;    return (F(a)+4*F(c)+F(b))*(b-a)/6;}inline double asr(const double &a,const double &b,const double &eps,const double &s) {    const double c=(a+b)/2,ls=simpson(a,c),rs=simpson(c,b);    if(fabs(ls+rs-s)<15*eps) return ls+rs+(ls+rs-s)/15;    return asr(a,c,eps/2,ls)+asr(c,b,eps/2,rs);}