前言
这篇文章仅用于存放各种模板，不写注释，具体原理请在 /ɔɪ:/ 查看。
正在汇总中……
缺省源
主要 tuple 是 C++17 的东西但是 CCF 的测评机可以编译通过，dSir 的似乎就不行。
缺省源
#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cerr<<#x<<':'<<(x)<<' '
#define dbe(x) cerr<<#x<<':'<<(x)<<endl
#define eb emplace_back
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using tp=tuple<int,int>;
int main(){
cin.tie(0)->sync_with_stdio(0);
return 0;
}对拍
这是 Linux 下的对拍。首先我们需要四个程序：code.cpp,bl.cpp,sj.cpp,dp.cpp。前两个一个放自己的程序一个放暴力程序，第三个放造数据的程序（每造一组数据 dp.cpp 都会给它传入一个数，需要将这个数设置为随机种子），都不用写文件输入输出。dp.cpp 里要写这个东西：
对拍
#include<bits/stdc++.h>
using namespace std;
int main(){
system("g++ -O2 code.cpp -o code -Wall -static -std=c++14");
system("g++ -O2 bl.cpp -o bl -Wall -static -std=c++14");
system("g++ -O2 sj.cpp -o sj -Wall -static -std=c++14");
int t=1e8;
for(int i=1;i<=t;i++){
FILE *fp=fopen("seed.in","w");
fprintf(fp,"%d",i);
fclose(fp);
system("./sj < seed.in > dp.in");
system("./bl < dp.in > dp.ans");
double st=clock();
system("./code < dp.in > dp.out");
double ed=clock();
cout<<i<<" "<<ed-st<<" ms\n";
if(system("diff dp.out dp.ans")){
cout<<"WA\n";
break;
}
}
return 0;
}离散化
C++
vi lsh;
//lsh.eb(someting);
sort(lsh.begin(),lsh.end());
lsh.resize(unique(lsh.begin(),lsh.end())-lsh.begin());
auto LSH=[&](int x){
return lower_bound(lsh.begin(),lsh.end(),x)-lsh.begin();
};STL
unordered_map
重定义哈希函数：
unordered_map
struct S{
unsigned int x,y;
bool operator==(S a)const{
return x==a.x&&y==a.y;
}
};
struct SHash{
ull operator()(S a)const{
return (a.x<<32)+a.y;
}
};
unordered_map<S,int,SHash>ma;数据结构
树状数组
bit
struct bit{
int n;
vi c;
bit(){}
bit(int n):n(n){
c.resize(n+1);
}
void add(int x,int d){
while(x<=n)c[x]+=d,x+=x&-x;
}
int cha(int x){
int ans=0;
while(x)ans+=c[x],x-=x&-x;
return ans;
}
int ef(int k){
int x=1<<(31-__builtin_clz(n)),sc=0;
while((x&-x)>1){
if(x>n||c[x]>=k)sc=x,x-=(x&-x)>>1;
else k-=c[x],x+=(x&-x)>>1;
}
return k-c[x]?sc:x;
}
};线段树
自己敲，看什么模板。
字符串
最小表示法
最小表示法
int n=s.size();
s=s+s;
int i=0,j=0,k=0;
while(i<n&&j<n&&k<n){
if(i==j)j++;
if(s[i+k]==s[j+k])k++;
else if(s[i+k]<s[j+k])j=j+k+1,k=0;
else i=i+k+1,k=0;
}manacher
manacher
vi d(n,1);
int p=0,r=1;
for(int i=1;i<n;i++){
if(i<r)d[i]=min(d[p-(i-p)],r-i+1);
while(i-d[i]>=0&&i+d[i]<n&&s[i-d[i]]==s[i+d[i]])d[i]++;
if(r<i+d[i]-1)r=i+d[i]-1,p=i;
}Z Algorithm
Z算法
vi z(n,0);
int l=0,r=0;
for(int i=1;i<n;i++){
if(i<r)z[i]=min(z[i-l],r-i+1);
while(i+z[i]<n&&s[z[i]]==s[i+z[i]])z[i]++;
if(i+z[i]-1>r)r=i+z[i]-1,l=i;
}
z[0]=n;KMP
KMP
vi pi(n+1);
for(int i=2;i<=n;i++){
int j=pi[i-1];
while(j>0&&s[j+1]!=s[i])j=pi[j];
j+=(s[j+1]==s[i]);
pi[i]=(j==i?0:j);
}数学&数论
快速幂
快速幂
int ksm(int a,int b){
int ans=1;
while(b){
if(b&1)ans=(ll)ans*a%P;
a=(ll)a*a%P;
b>>=1;
}
return ans;
}线性筛
线性筛
vi prm,v(N+1);
for(int i=2;i<=N;i++){
if(v[i]==0)v[i]=i,prm.emplace_back(i);
for(auto p:prm){
if(p*i>N||v[i]<p)break;
v[i*p]=p;
}
}EXGCD
做了些许简化。
C++
function<int(int,int,ll&,ll&)>exgcd=[&](int a,int b,ll& x,ll& y){
if(b==0){x=1,y=0;return a;}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
};线性组合计数(线性求逆元)
功能有快速幂，求 inv[i],fct[i],invfct[i]，求 $\binom{n}{m}$ 和 $\binom{n}{a_1,a_2,\dots ,a_k}$。放在main函数外面,记得使用前要调用init初始化。
线性求逆元
const int P=1e9+9;
namespace modint{
vi fct,inv,invfct;
int ksm(int a,int b){
int ans=1;
while(b){
if(b&1)ans=(ll)ans*a%P;
a=(ll)a*a%P;
b>>=1;
}
return ans;
}
void init(int n){
fct.resize(n+1);
inv.resize(n+1);
invfct.resize(n+1);
fct[0]=1;
for(int i=1;i<=n;i++){
fct[i]=(ll)fct[i-1]*i%P;
}
invfct[n]=ksm(fct[n],P-2);
for(int i=n;i>=1;i--){
inv[i]=(ll)fct[i-1]*invfct[i]%P;
invfct[i-1]=(ll)i*invfct[i]%P;
}
}
int binom(int n,int m){
return (ll)fct[n]*invfct[m]%P*invfct[n-m]%P;
}
int binom(int n,vi m){
int ans=fct[n];
for(auto v:m){
ans=(ll)ans*invfct[v]%P;
}
return ans;
}
}
using namespace modint;整数分块
整数分块
int sum=0;
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
sum+=(r-l+1)*(n/l);
}矩阵乘法
矩阵乘法
struct JZ{
vector<vl>a;
int n,m;
JZ(){}
JZ(vector<vl>&a):a(a),n(a.size()){
m=(a.size()?a[0].size():0);
}
JZ(int n,int m):n(n),m(m){
a.resize(n,vl(m));
}
friend JZ operator*(const JZ& a,const JZ& b){
vector<vl>c(a.n,vl(b.m));
for(int i=0;i<a.n;i++){
for(int j=0;j<b.m;j++){
for(int k=0;k<a.m;k++){
c[i][j]+=a.a[i][k]*b.a[k][j];//
}
}
}
return c;
}
};