本文使用 $\LaTeX$ 语法。若出现渲染失败或错误,请刷新页面并耐心等待刷新完成。

NOI系列考试、本地通用编译命令

-Wall -lm -O2 --std=c++14 -Dght -Wl,--stack=268435456 -fsanitize= -Dwo_ai_feicheng

本博客所有题解都建立在此基础上。

C++系IOの关闭流同步

ios::sync_with_stdio(0);
cin.tie(0);

可以使cincout速率变得更快。

取模优化

虽然看着不起眼,但优化效果很离谱。尤其对是快速幂取模这种取模运算量极大的函数。

inline int qmod(int x){return x-md*(x/md);}

或者

inline int qmod(int x){return x>=md?x-md:x;}

负数取模

inline int qmod(int x){return x>=md?x-md:x;}
inline int qmo(int y){return qmod(qmod(y)+md);}

快速幂

#define md 1000000007
int qpow(int a,int b){
    int ret=qpow(a,b>>1)%md;
    return (b&1?a:1)*ret*ret%md;
}

费马小定理与逆元

费马小定理:假如 $a$ 是一个整数,$p$ 是一个质数,那么

  • a是p的倍数:$a^p\equiv a\ (\textrm{mod}\ p)$

  • a不是是p的倍数:$a^{p-1}\equiv 1\ (\textrm{mod}\ p)$。

逆元:

  • 对于正整数 $a$, $p$,如果有$ax\equiv 1(\textrm{mod}\ p)$,那么 $x$ 的最小正整数解为 $a$ 模 $p$ 的逆元。

  • 对于素数 $p$,则逆元 $x=a^{p-2}\textrm{mod}p$。

  • 不重要的证明:$a^{p-1}\equiv 1(\textrm{mod}\ p) \Rightarrow a^{p-2}\equiv \frac{1}{a}(\textrm{mod}\ p) $。

那么快速幂狂解就完事了。

int inv(int a){
    return qpow(a,md-2);
}

自从C++11被丢进来的lambda

主要运用在结构体的memset中装X

sort(a+1,a+1+n,[](node x,node y){return x.s>y.s;});//lambda就是后面这一串玩意。

手写lowbit函数

找一个数二进制下最低是 $1$ 的位。

比某臭名昭著的库里的函数快了亿点点。

inline int lowbit(int n){return n&(-n);}

当在评测机上想搞一些奇怪的东西时

我们先前提到的编译命令里有:-Dght这一条。

于是我们可以这样:

#ifndef ght
//Anything to code
#endif

或者这样:

#ifndef fuck_ccf
//禁赛三年警告
#endif

并加上-Dfuck_ccf

这样,本地就不会运行这段代码,而评测机肯定不会搞这么一个奇怪的编译命令,所以会在其中运行。

我在加速评测机的输入输出一文所引用的fread快读就利用了这个原理,摘抄如下:

#ifdef ONLINE_JUDGE
#define getchar()(in_p1==in_p2&&(in_p2=(in_p1=in_buf)+fread(in_buf,1,bufSIZE,stdin),in_p1==in_p2)?EOF:*in_p1++)
char in_buf[bufSIZE],*in_p1=in_buf,*in_p2=in_buf;
#endif

当然,这段代码的第一行最好还是改成:

#ifndef ght

尤其是在竞赛或民间评测机评测时。蒟蒻已经在€€£的考试中试过了,亲试可行。

int128

如它的名字,这是一个数字存储大小甚至是long long int两倍的声明。

不过代价则是,他牺牲了空间和敲代码的时间。空间为16B,也就是int的4倍,对于一个 Memory Limit 256MB 的题来说很不友好,开个 $2\times 10^7$ 就会炸掉爆〇。况且,所有传统的io都无法输入输出一个__int128声明类型的数,必须打出一份类似快读快写的代码才能做到。

最关键的则是,使用这个又臭又长的东西,几乎完全不能避免该有的高精度问题。你想想,毒瘤出题人会不把他拿捏得死死的?

但我要AFO了。无所畏惧。

GCC提供了两种128位整数类型,分别是__int128_t__uint128_t,分别用于声明有符号整数变量和无符号整数变量。

当然,你也可以直接上__int128

首先我们不妨试下,传统意义上挺万能的C++系io会把他们输出成啥玩意。

    __int128_t a;
    cin>>a;
    cout<<a;
[Error] no match for 'operator>>' (operand types are 'std::istream' {aka 'std::basic_istream<char>'} and '__int128')

行吧,果然没用。那么我们来写一份快读快写

    __int128 a;
    redi(a);
    wrti(a);

Wow, it works well!

当然,考试的话写这么一大串的快读快写是不现实的。这里还有一份简单版。实测正负都可以哦。

正在更新···


The Only Thing That's Changed is EVERYTHING .