模板库

缺省源

-Wall -Wextra -Wunused -Wl,--stack=1024000000 --std=c++11 -O0 -D LOCAL

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<ctime>
#include<assert.h>
#define _INT_INF ((int)0x3f3f3f3f)
#define _UINT_MAX ((unsigned int)0xffffffff)
#define _INT_MAX ((int)0x7fffffff)
#define _LL_INF ((long long)0x3f3f3f3f3f3f3f3f)
#define _ULL_MAX ((unsigned long long)0xffffffffffffffff)
#define _LL_MAX ((long long)0x7fffffffffffffff)
namespace FastIO{
#ifdef LOCAL
	#define getChar getchar()
#else
	#define BUF_SIZE 33554432
	char __buff__[BUF_SIZE];char *__p1__=__buff__,*__p2__=__buff__;
	#define getChar (__p1__==__p2__&&(__p2__=(__p1__=__buff__)+fread(__buff__,1,BUF_SIZE,stdin),__p1__==__p2__)?EOF:*__p1__++)
#endif
	inline int read(){register int x=0;register char c=getChar;while(c<'0'||c>'9')c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return x;}inline int reads(){register int x=0,y=1;register char c=getChar;while(c<'0'||c>'9')y&=(c!='-'),c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return y?x:-x;}inline long long readl(){register long long x=0;register char c=getChar;while(c<'0'||c>'9')c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return x;}inline int readsl(){register long long x=0;register int y=1;register char c=getChar;while(c<'0'||c>'9')y&=(c!='-'),c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return y?x:-x;}inline void read(char *s){register char c=getChar;while(c=='\n'||c=='\r'||c==' '||c=='\t') c=getChar;while(c!='\n'&&c!='\r'&&c!=' '&&c!='\t'&&c!=EOF) *s=c,s++,c=getChar;*s=0;}
	#undef getChar
	#define EN print('\n')
	#define SPACE print(' ')
#ifdef LOCAL
	#define RET 0
	inline void print(register int x){printf("%d",x);}inline void printEN(register int x){printf("%d\n",x);}inline void printSP(register int x){printf("%d ",x);}inline void print(register long long x){printf("%lld",x);}inline void printEN(register long long x){printf("%lld\n",x);}inline void printSP(register long long x){printf("%lld ",x);}inline void print(register char c){printf("%c",c);}inline void print(const char *c){printf("%s",c);}
#else
	#undef BUF_SIZE
	#define RET fwrite(__buffW__,1,__bb__,stdout),0
	#define BUFW_SIZE 33554432
	char __buffW__[BUFW_SIZE];int __bb__;char __stack__[28];inline void print(register int x,register short base=10){if(!x)return __buffW__[__bb__++]='0',void();if(x<0)__buffW__[__bb__++]='-',x=-x;register short top=0;while(x)__stack__[++top]=(x%base)^48,x/=base;while(top)__buffW__[__bb__++]=__stack__[top--];}inline void printEN(register int x,register short base=10){if(!x)return __buffW__[__bb__++]='0',__buffW__[__bb__++]='\n',void();if(x<0)__buffW__[__bb__++]='-',x=-x;register short top=0;while(x)__stack__[++top]=(x%base)^48,x/=base;while(top)__buffW__[__bb__++]=__stack__[top--];__buffW__[__bb__++]='\n';}inline void printSP(register int x,register short base=10){if(!x)return __buffW__[__bb__++]='0',__buffW__[__bb__++]=' ',void();if(x<0)__buffW__[__bb__++]='-',x=-x;register short top=0;while(x)__stack__[++top]=(x%base)^48,x/=base;while(top)__buffW__[__bb__++]=__stack__[top--];__buffW__[__bb__++]=' ';}inline void print(register long long x,register short base=10){if(!x)return __buffW__[__bb__++]='0',void();if(x<0)__buffW__[__bb__++]='-',x=-x;register short top=0;while(x) __stack__[++top]=(x%base)^48,x/=base;while(top)__buffW__[__bb__++]=__stack__[top--];}inline void printEN(register long long x,register short base=10){if(!x)return __buffW__[__bb__++]='0',__buffW__[__bb__++]='\n',void();if(x<0)__buffW__[__bb__++]='-',x=-x;register short top=0;while(x) __stack__[++top]=(x%base)^48,x/=base;while(top)__buffW__[__bb__++]=__stack__[top--];__buffW__[__bb__++]='\n';}inline void printSP(register long long x,register short base=10){if(!x)return __buffW__[__bb__++]='0',__buffW__[__bb__++]=' ',void();if(x<0)__buffW__[__bb__++]='-',x=-x;register short top=0;while(x) __stack__[++top]=(x%base)^48,x/=base;while(top)__buffW__[__bb__++]=__stack__[top--];__buffW__[__bb__++]=' ';}inline void print(register char c){__buffW__[__bb__++]=c;}inline void print(const char *c){while(*c)__buffW__[__bb__++]=*c,c++;}
	#undef BUFW_SIZE
#endif
}/*namespace FastIO*/using namespace FastIO;
namespace lib{__attribute__((always_inline))inline void chkMin(int &a,const int &b){(a>b)&&(a=b);}__attribute__((always_inline))inline void chkMin(long long &a,const long long &b){(a>b)&&(a=b);}__attribute__((always_inline))inline void chkMax(int &a,const int &b){(a<b)&&(a=b);}__attribute__((always_inline))inline void chkMax(long long &a,const long long &b){(a<b)&&(a=b);}__attribute__((always_inline))inline int min(const int &a,const int &b){return a>b?b:a;}__attribute__((always_inline))inline long long min(const long long &a,const long long &b){return a>b?b:a;}__attribute__((always_inline))inline int max(const int &a,const int &b){return a>b?a:b;}__attribute__((always_inline))inline long long max(const long long &a,const long long &b){return a>b?a:b;}__attribute__((always_inline))inline void swap(int &a,int &b){a^=b;b^=a;a^=b;}__attribute__((always_inline))inline void swap(long long &a,long long &b){a^=b;b^=a;a^=b;}__attribute__((always_inline))inline int abs(const int &a){return a>0?a:-a;}__attribute__((always_inline))inline long long abs(const long long &a){return a>0?a:-a;}}
int main(){
	return RET;
}

对拍

Linux 版：

#include<cstdio>
#include<algorithm>
#include<ctime>
int main(){
	for(int i=1;;i++){
		printf("-------------- test %d ---------------\n",i);
		puts("run mk.exe");
		if(system("./mk > in.txt")) return puts("mk.exe RE"),1;
		puts("run A.exe");
		long long tt=clock();
		if(system("./a < in.txt > A.txt")) return puts("A.exe RE"),1;
		printf("A.exe used %lldms\n",clock()-tt);
		tt=clock();
		puts("run B.exe");
		if(system("./std < in.txt > B.txt")) return puts("B.exe RE"),1;
		printf("B.exe used %lldms\n",clock()-tt);
		if(system("diff -w A.txt B.txt")) return puts("WA"),1;
	}
	return 0;
}

Windows 版：

#include<cstdio>
#include<algorithm>
#include<ctime>
int main(){
	for(int i=1;;i++){
		printf("-------------- test %d ---------------\n",i);
		puts("run mk.exe");
		if(system("mk.exe > in.txt")) return puts("mk.exe RE"),1;
		puts("run A.exe");
		long long tt=clock();
		if(system("A.exe < in.txt > A.txt")) return puts("A.exe RE"),1;
		printf("A.exe used %lldms\n",clock()-tt);
		tt=clock();
		puts("run B.exe");
		if(system("B.exe < in.txt > B.txt")) return puts("B.exe RE"),1;
		printf("B.exe used %lldms\n",clock()-tt);
		if(system("fc A.txt B.txt")) return puts("WA"),1;
	}
	return 0;
}

图论：https://www.cnblogs.com/suxxsfe/p/15987120.html

数据结构：https://www.cnblogs.com/suxxsfe/p/15987128.html

数学、计算几何、字符串：https://www.cnblogs.com/suxxsfe/p/15987139.html

其他

快速幂

inline long long power(long long a,long long b,long long mod=MOD){
	long long ans=1;
	while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
	return ans;
}

取模

inline long long power(long long a,long long b,long long mod=MOD){
	long long ans=1;
	while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
	return ans;
}
struct ModInt{
	long long x;
#define inline __attribute__((always_inline))
	inline ModInt operator - (){return {x?(MOD-x):0};}
	inline ModInt operator - (const ModInt &o){return {(x-o.x<0)?(x-o.x+MOD):(x-o.x)};}
	inline ModInt operator - (const int &o){return {(x-o<0)?(x-o+MOD):(x-o)};}
	inline void operator -= (const ModInt &o){x=(x-o.x<0)?(x-o.x+MOD):(x-o.x);}
	inline void operator -= (const int &o){x=(x-o<0)?(x-o+MOD):(x-o);}
	inline friend ModInt operator - (const int &a,const ModInt &b){return {(a-b.x<0)?(a-b.x+MOD):(a-b.x)};}
	inline void operator -- (int){x--;if(x<0) x=MOD-1;}
	inline ModInt operator + (const ModInt &o){return {(x+o.x>=MOD)?(x+o.x-MOD):(x+o.x)};}
	inline ModInt operator + (const int &o){return {(x+o>=MOD)?(x+o-MOD):(x+o)};}
	inline void operator += (const ModInt &o){x=(x+o.x>=MOD)?(x+o.x-MOD):(x+o.x);}
	inline void operator += (const int &o){x=(x+o>=MOD)?(x+o-MOD):(x+o);}
	inline friend ModInt operator + (const int &a,const ModInt &b){return {(b.x+a>=MOD)?(b.x+a-MOD):(b.x+a)};}
	inline void operator ++ (int){x++;if(x==MOD) x=0;}
	inline ModInt operator * (const ModInt &o){return {x*o.x%MOD};}
	inline ModInt operator * (const int &o){return {x*o%MOD};}
	inline void operator *= (const ModInt &o){x=x*o.x%MOD;}
	inline void operator *= (const int &o){x=x*o%MOD;}
	inline friend ModInt operator * (const int &a,const ModInt &b){return {a*b.x%MOD};}
	inline ModInt operator / (const ModInt &o){return {x*power(o.x,MOD-2)%MOD};}
	inline ModInt operator / (const int &o){return {x*power(o,MOD-2)%MOD};}
	inline void operator /= (const ModInt &o){x=x*power(o.x,MOD-2)%MOD;}
	inline void operator /= (const int &o){x=x*power(o,MOD-2)%MOD;}
	inline friend ModInt operator / (const int &a,const ModInt &b){return {a*power(b.x,MOD-2)%MOD};}
	inline void operator = (const int &a){x=a;}
	inline int operator == (const ModInt &o){return x==o.x;}
	inline int operator == (const int &o){return x==o;}
#undef inline
};
inline ModInt power(ModInt a,long long b){
	ModInt ans;ans=1;
	while(b){if(b&1) ans=ans*a;a=a*a;b>>=1;}
	return ans;
}

fread 和 fwrite

namespace FastIO{
	#define inline __attribute__((always_inline)) inline
#ifdef LOCAL
	#define getChar getchar()
#else
	#define BUF_SIZE 33554432
	char __buff__[BUF_SIZE];char *__p1__=__buff__,*__p2__=__buff__;
	#define getChar (__p1__==__p2__&&(__p2__=(__p1__=__buff__)+fread(__buff__,1,BUF_SIZE,stdin),__p1__==__p2__)?EOF:*__p1__++)
#endif
	inline int read(){
		register int x=0;register char c=getChar;
		while(c<'0'||c>'9')	c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return x;
	}
	inline int reads(){
		register int x=0,y=1;register char c=getChar;
		while(c<'0'||c>'9') y&=(c!='-'),c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return y?x:-x;
	}
	inline long long readl(){
		register long long x=0;register char c=getChar;
		while(c<'0'||c>'9') c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return x;
	}
	inline int readsl(){
		register long long x=0;register int y=1;register char c=getChar;
		while(c<'0'||c>'9') y&=(c!='-'),c=getChar;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getChar;return y?x:-x;
	}
	inline void read(char *s){
		register char c=getChar;while(c=='\n'||c=='\r'||c==' '||c=='\t') c=getChar;
        while(c!='\n'&&c!='\r'&&c!=' '&&c!='\t'&&c!=EOF) *s=c,s++,c=getChar;*s=0;
	}
	#undef getChar
	#define EN write('\n')
	#define SPACE write(' ')
#ifdef LOCAL
	#define RET 0
	inline void write(register int x){printf("%d",x);}
	inline void writeEN(register int x){printf("%d\n",x);}
	inline void writeSP(register int x){printf("%d ",x);}
	inline void write(register long long x){printf("%lld",x);}
	inline void writeEN(register long long x){printf("%lld\n",x);}
	inline void writeSP(register long long x){printf("%lld ",x);}
	inline void write(register char c){printf("%c",c);}
	inline void write(const char *c){printf("%s",c);}
#else
	#undef BUF_SIZE
	#define RET fwrite(__buffW__,1,__bb__,stdout),0
	#define BUFW_SIZE 33554432
	char __buffW__[BUFW_SIZE];int __bb__;
	char __stack__[28];
	inline void write(register int x,register short base=10){
		if(!x) return __buffW__[__bb__++]='0',void();if(x<0) __buffW__[__bb__++]='-',x=-x;
		register short top=0;
		while(x) __stack__[++top]=(x%base)^48,x/=base;while(top) __buffW__[__bb__++]=__stack__[top--];
	}
	inline void writeEN(register int x,register short base=10){
		if(!x) return __buffW__[__bb__++]='0',__buffW__[__bb__++]='\n',void();if(x<0) __buffW__[__bb__++]='-',x=-x;
		register short top=0;
		while(x) __stack__[++top]=(x%base)^48,x/=base;while(top) __buffW__[__bb__++]=__stack__[top--];__buffW__[__bb__++]='\n';
	}
	inline void writeSP(register int x,register short base=10){
		if(!x) return __buffW__[__bb__++]='0',__buffW__[__bb__++]=' ',void();if(x<0) __buffW__[__bb__++]='-',x=-x;
		register short top=0;
		while(x) __stack__[++top]=(x%base)^48,x/=base;while(top) __buffW__[__bb__++]=__stack__[top--];__buffW__[__bb__++]=' ';
	}
	inline void write(register long long x,register short base=10){
		if(!x) return __buffW__[__bb__++]='0',void();if(x<0) __buffW__[__bb__++]='-',x=-x;
		register short top=0;
		while(x) __stack__[++top]=(x%base)^48,x/=base;while(top) __buffW__[__bb__++]=__stack__[top--];
	}
	inline void writeEN(register long long x,register short base=10){
		if(!x) return __buffW__[__bb__++]='0',__buffW__[__bb__++]='\n',void();if(x<0) __buffW__[__bb__++]='-',x=-x;
		register short top=0;
		while(x) __stack__[++top]=(x%base)^48,x/=base;while(top) __buffW__[__bb__++]=__stack__[top--];__buffW__[__bb__++]='\n';
	}
	inline void writeSP(register long long x,register short base=10){
		if(!x) return __buffW__[__bb__++]='0',__buffW__[__bb__++]=' ',void();if(x<0) __buffW__[__bb__++]='-',x=-x;
		register short top=0;
		while(x) __stack__[++top]=(x%base)^48,x/=base;while(top) __buffW__[__bb__++]=__stack__[top--];__buffW__[__bb__++]=' ';
	}
	inline void write(register char c){__buffW__[__bb__++]=c;}
	inline void write(const char *c){while(*c) __buffW__[__bb__++]=*c,c++;}
	#undef BUFW_SIZE
#endif
#undef inline
}//namespace FastIO

高精度，压位每位 \(32768\)，可以除单精，模单精，减高精，其他运算均同时支持高精、单精
不支持负数、不能读入、不能输出
其中单精指小于 \(32768\) 的数，即使是同时支持单精、高精的运算，大于 \(32768\) 的数也需转高精运算
作为局部变量声明后尽量调用 xxx.clear()

struct BigInt{
#define BASE 32768
#define SIZE 85
	long long a[SIZE];
	inline BigInt(){a[0]=1;}
	inline long long operator [] (const int &pos)const{return a[pos];}
	inline long long &operator [] (const int &pos){return a[pos];}
	inline void clear(){__builtin_memset(a,0,sizeof a);a[0]=1;}
	inline void init(){a[0]=1;}
	inline void operator = (const BigInt &o){__builtin_memcpy(a,o.a,sizeof a);}
	inline void operator = (long long o){
		if(!o) return;
		a[0]=0;
		while(o) a[++a[0]]=o%BASE,o/=BASE;
	}
	inline long long toLL(){
		long long ans=0;
		for(int i=a[0];i;i--) ans=ans*BASE+a[i];
		return ans;
	}
	inline void refresh(){
		for(int i=a[0]+1;i<SIZE;i++) a[i]=0;
		for(int i=1;i<=a[0];i++) a[i+1]+=a[i]/BASE,a[i]%=BASE;
		while(a[a[0]+1]) a[0]++,a[a[0]+1]+=a[a[0]]/BASE,a[a[0]]%=BASE;
		while(!a[a[0]]&&a[0]>1) a[0]--;
	}
	inline BigInt operator + (const BigInt &o){
		BigInt ans;ans=*this;
		for(int i=1;i<=o[0];i++) ans[i]+=o[i];lib::chkMax(ans[0],o[0]);
		ans.refresh();
		return ans;
	}
	inline void operator += (const BigInt &o){
		for(int i=1;i<=o[0];i++) a[i]+=o[i];lib::chkMax(a[0],o[0]);refresh();
	}
	inline BigInt operator + (const long long &o){
		BigInt ans;ans=*this;
		ans[1]+=o;ans.refresh();
		return ans;
	}
	inline void operator += (const long long &o){
		a[1]+=o;refresh();
	}
	inline BigInt operator - (const BigInt &o){
		BigInt ans;ans=*this;
		for(int i=1;i<=o[0];i++){
			ans[i]-=o[i];
			if(ans[i]<0) ans[i]+=BASE,ans[i+1]--;
		}
		ans.refresh();
		return ans;
	}
	inline void operator -= (const BigInt &o){
		for(int i=1;i<=o[0];i++){
			a[i]-=o[i];
			if(a[i]<0) a[i]+=BASE,a[i+1]--;
		}
		refresh();
	}
	inline BigInt operator * (const BigInt &o){
		BigInt ans;ans.clear();
		for(int i=1;i<=a[0];i++)for(int j=1;j<=o[0];j++) ans[i+j-1]+=a[i]*o[j];ans[0]=a[0]+o[0]-1;
		ans.refresh();
		return ans;
	}
	inline void operator *= (const BigInt &o){
		*this=*this*o;
	}
	inline BigInt operator * (const long long &o){
		BigInt ans;ans.clear();ans[0]=a[0];
		for(int i=1;i<=a[0];i++) ans[i]=a[i]*o;ans.refresh();
		return ans;
	}
	inline void operator *= (const long long &o){
		for(int i=1;i<=a[0];i++) a[i]*=o;refresh();
	}
	inline BigInt operator / (const long long &o){
		BigInt ans,copy;ans.clear();copy=*this;
		int back=a[0];
		for(int i=a[0];i;i--) ans[i]=copy[i]/o,copy[i-1]+=(copy[i]%o)*BASE;
		ans[0]=back;ans.refresh();
		return ans;
	}
	inline void operator /= (const long long &o){
		int back=a[0];
		for(int i=a[0];i;i--) a[i-1]+=(a[i]%o)*BASE,a[i]/=o;
		a[0]=back;refresh();
	}
	inline long long operator % (const long long &o){
		return (*this-(*this/o)*o).toLL();
	}
	inline int operator < (const BigInt &b){
		if(a[0]^b[0]) return a[0]<b[0];
		for(int i=a[0];i;i--)if(a[i]^b[i]) return a[i]<b[i];
		return 0;
	}
	inline int operator <= (const BigInt &b){
		if(a[0]^b[0]) return a[0]<b[0];
		for(int i=a[0];i;i--)if(a[i]^b[i]) return a[i]<b[i];
		return 1;
	}
	inline int operator > (const BigInt &b){
		if(a[0]^b[0]) return a[0]>b[0];
		for(int i=a[0];i;i--)if(a[i]^b[i]) return a[i]>b[i];
		return 0;
	}
	inline int operator >= (const BigInt &b){
		if(a[0]^b[0]) return a[0]>b[0];
		for(int i=a[0];i;i--)if(a[i]^b[i]) return a[i]>b[i];
		return 1;
	}
#undef BASE
#undef SIZE
};

快速排序

使用 sort

模板库

其他

推荐阅读