前言

这篇文章仅用于存放各种模板，不写注释，具体原理请在 /ɔɪ:/ 查看。

正在汇总中……

缺省源

主要 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;
}

离散化

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

重定义哈希函数：

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;

数学&数论

快速幂

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

做了些许简化。

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);
}