前言

编译选项：

-std=gnu++17 -O2

使用该模板时，请在程序开头加上如下语句：

#include<bits/stdc++.h>
using namespace std;

现较完善模板已有：快速 IO、并查集、ST 表、树状数组、普通线段树、扫描线、数论相关等内容。

Upd on 2024.10.13：添加了“命题相关模板”一栏。

本模板库在部分问题上参考了 AtCoder Library 的处理方式。

第一部分 较完善模板

快速 IO（Fast IO）

namespace IAOI_lib{
  typedef long long ll;
  inline int read(){
    int x=0; char c=getchar(); bool f=false;
    while(!isdigit(c)){
      if(c=='-')f=true;
      c=getchar();
    }
    while(isdigit(c)){
      x=(x<<1)+(x<<3)+(c^48);
      c=getchar();
    }
    return f?-x:x;
  }
  inline void write(int x){
    if(x<0){putchar('-'); write(-x); return;}
    if(x/10)write(x/10);  putchar(x%10+48);
  }
  inline ll readll(){
    ll x=0; char c=getchar(); bool f=false;
    while(!isdigit(c)){
      if(c=='-')f=true;
      c=getchar();
    }
    while(isdigit(c)){
      x=(x<<1)+(x<<3)+(c^48);
      c=getchar();
    }
    return f?-x:x;
  }
  inline void writell(ll x){
    if(x<0){putchar('-'); write(-x); return;}
    if(x/10)writell(x/10);  putchar(x%10+48);
  }
}

功能介绍

• int read() / long long readll()：从标准输入读取一个整数；
• int write() / long long writell()：向标准输出写入一个整数。

示例代码

P9515「JOC-1A」签到题 by FFTotoro

并查集（DSU）

namespace IAOI_lib{
  template<typename T> class dsu{
    private:
      vector<T> a;
      vector<int> s;
    public:
      dsu(int n=2e5){
        a.resize(n),s.resize(n,1);
        iota(a.begin(),a.end(),0);
      }
      T leader(T x){
        return a[x]==x?x:a[x]=leader(a[x]);
      }
      inline int size(T x){
        return s[leader(x)];
      }
      inline void merge(T x,T y){
        x=leader(x),y=leader(y);
        if(x==y)return;
        if(s[x]>s[y])swap(x,y);
        s[y]+=s[x],a[x]=y;
      }
      inline bool same(T x,T y){
        return leader(x)==leader(y);
      }
  };
}

功能介绍

UPD：增加了带权功能（即维护连通块大小）。

• dsu<T> d(int n)：创建一个大小为 n(1\le n\le 10^8)（如果不添加 (int n) 则为默认大小 2\times 10^5）、存储类型为 T 的并查集，时间复杂度 O(n)（下文 x,y 的范围均为 0\le x,y<n）；
• T d.leader(T x)：返回 x 的祖先，时间复杂度 O(\alpha(n))；
• int d.size(T x)：返回 x 所在连通块（集合）的大小，时间复杂度 O(\alpha(n))；
• void d.merge(T x,T y)：合并 x 和 y 所在的连通块（集合），时间复杂度 O(\alpha(n))；
• bool d.same(T x,T y)：返回 x 和 y 是否在同一个连通块（集合）内，时间复杂度 O(\alpha(n))。

示例代码

P9488 ZHY 的生成树 by FFTotoro

ST 表（Sparse Table）

namespace IAOI_lib{
  template<typename T,T(*op)(T,T)> class sparse_table{
    private:
      vector<vector<T> > s;
    public:
      sparse_table(vector<T> a){
        int k=__lg(a.size());
        s.resize(a.size(),vector<T>(k+1));
        for(int i=0;i<a.size();i++)
          s[i][0]=a[i];
        for(int i=1;i<=k;i++)
          for(int j=0;j+(1<<i)<=a.size();j++)
            s[j][i]=op(s[j][i-1],s[j+(1<<i-1)][i-1]);
      }
      inline T query(int l,int r){
        int k=__lg(r-l+1);
        return op(s[l][k],s[r-(1<<k)+1][k]);
      }
  };
}

功能介绍

• sparse_table<T,op> s(vector<T> a)：对于存储 T 类型的 a 数组（std::vector）创建一个 ST 表，op 为你需要维护的操作（特别地，它需要满足消去律 \mathrm{op}(x,x)=x；例如，\gcd、\max、\mathrm{and} 等都满足消去律），时间复杂度 O(n\log n)，这里 n(1\le n\le 2\times 10^6) 为 a 的大小；
• T s.query(int l,int r)：返回 \mathrm{op}_{i=l}^r a_i 的值，时间复杂度 O(1)。

示例代码

P2412 查单词 by FFTotoro

树状数组（Fenwick Tree）

namespace IAOI_lib{
  template<typename T> class fenwick_tree{
    private:
      vector<T> t;
    public:
      fenwick_tree(int n=2e5){
        t.resize(n);
      }
      inline int lowbit(int x){
        return x&-x;
      }
      inline void add(int p,T d){
        t[p++]+=d;
        while((p+=lowbit(p))<=t.size())t[p-1]+=d;
      }
      inline T pre_sum(int p){
        T s=t[p++];
        while((p-=lowbit(p))>0)s+=t[p-1];
        return s;
      }
      inline T sum(int l,int r){
        return pre_sum(r)-(l?pre_sum(l-1):0);
      }
  };
}

功能介绍

• fenwick_tree<T> t(int n)：创建一个大小为 n(1\le n\le 10^8)、存储类型为 T 的树状数组，时间复杂度 O(n)；
• void t.add(int p,T d)：向树状数组 t 中的第 p(0\le p<n) 个元素加上 d，时间复杂度 O(\log n)；
• T t.sum(int l,int r)：返回 \sum\limits_{i=l}^r a_i(0\le l\le r<n)，时间复杂度 O(\log n)。

示例代码

P3970 [TJOI2014] 上升子序列 by FFTotoro

普通线段树（Segtree）

namespace IAOI_lib{
  template<typename S,S(*op)(S,S),S(*e)()> class segtree{
    private:
      typedef pair<int,int> pii;
      vector<pii> B;
      vector<S> R;
      inline void pushup(int u){
        R[u]=op(R[u<<1],R[u<<1|1]);
      }
    public:
      segtree(int n){
        B.resize(n<<2),R.resize(n<<2);
        function<void(int,int,int)> build=[&](int u,int l,int r){
          if(B[u]=make_pair(l,r);l==r){R[u]=e(); return;}
          int m=l+r>>1;
          build(u<<1,l,m),build(u<<1|1,m+1,r);
          pushup(u);
        };
        build(1,0,n-1);
      }
      segtree(vector<S> a){
        B.resize(a.size()<<2),R.resize(a.size()<<2);
        function<void(int,int,int)> build=[&](int u,int l,int r){
          if(B[u]=make_pair(l,r);l==r){R[u]=a[l]; return;}
          int m=l+r>>1;
          build(u<<1,l,m),build(u<<1|1,m+1,r);
          pushup(u);
        };
        build(1,0,a.size()-1);
      }
      inline void set(int p,S x,int u=1){
        if(B[u].first==B[u].second){R[u]=x; return;}
        int m=B[u].first+B[u].second>>1;
        set(p,x,u<<1|(p>m)),pushup(u);
      }
      inline S get(int p,int u=1){
        if(B[u].first==B[u].second)return R[u];
        int m=B[u].first+B[u].second>>1;
        return get(p,u<<1|(p>m));
      }
      inline S prod(int l,int r,int u=1){
        if(B[u].first>r||B[u].second<l)return e();
        if(l<=B[u].first&&B[u].second<=r)return R[u];
        return op(prod(l,r,u<<1),prod(l,r,u<<1|1));
      }
      inline S all_prod(){return R[1];}
  };
}

功能介绍

• segtree<S,op,e> s(int n) / segtree<S,op,e> s(vector<S> a)：创建一个存储类型为 S，操作为 op，幺元为 e 的线段树，时间复杂度 O(n)；
• void set(int p,S x)：单点修改位置 p 上的元素为 x，时间复杂度 O(\log n)；
• S get(int p)：查询位置 p 上的元素，时间复杂度 O(\log n)；
• S prod(int l,int r)：返回 \mathrm{op}_{i=l}^r a_i，时间复杂度 O(\log n)；
• S all_prod()：返回 \mathrm{op}_{i=0}^{n-1} a_i，时间复杂度 O(1)。

矩形面积并（Atlantis）

namespace IAOI_lib{
#define int long long
  class atlantis{
    typedef pair<int,int> pii;
    typedef tuple<int,int,int,int> tpi;
    private:
      struct line{
        int l,r,h,s;
        bool operator <(const line &x)const{
          return h<x.h;
        }
      };
      int n;
      vector<line> L;
      vector<pii> B;
      vector<int> X,C,S;
      void build(int u,int l,int r){
        if(B[u]=make_pair(l,r);l==r)return;
        int m=l+r>>1;
        build(u<<1,l,m),build(u<<1|1,m+1,r);
        pushup(u);
      }
      inline void pushup(int u){
        if(C[u])S[u]=X[B[u].second+1]-X[B[u].first];
        else S[u]=S[u<<1]+S[u<<1|1];
      }
      void update(int u,int l,int r,int c){
        if(X[B[u].second+1]<=l||r<=X[B[u].first])return;
        if(l<=X[B[u].first]&&X[B[u].second+1]<=r)C[u]+=c;
        else update(u<<1,l,r,c),update(u<<1|1,l,r,c);
        pushup(u);
      }
      int all_prod(){return S[1];}
    public:
      int areas_union(vector<tpi> a){
        X.resize(a.size()<<1),L.resize(a.size()<<1);
        for(int i=0;i<a.size();i++){
          auto &[xa,ya,xb,yb]=a[i];
          if(xa>xb)swap(xa,xb); if(ya>yb)swap(ya,yb);
          X[i<<1]=xa,X[i<<1|1]=xb;
          L[i<<1]=(line){xa,xb,ya,1},L[i<<1|1]=(line){xa,xb,yb,-1};
        }
        sort(L.begin(),L.end(),[](line x,line y){return x.h<y.h;});
        sort(X.begin(),X.end()),n=unique(X.begin(),X.end())-X.begin();
        B.resize(n<<2),C.resize(n<<2),S.resize(n<<3),build(1,0,n-2);
        int c=0;
        for(int i=0;i+1<a.size()<<1;i++){
          update(1,L[i].l,L[i].r,L[i].s);
          c+=all_prod()*(L[i+1].h-L[i].h);
        }
        return c;
      }
  };
#undef int
}

功能介绍

• long long atlantis(vector<tuple<long long,long long,long long,long long> > a)：求若干个四边平行于坐标轴的矩形的面积并。

示例代码

P10096 [ROIR 2023 Day 1] 扫地机器人 by FFTotoro

数论（Number Theory）

namespace IAOI_lib{
  typedef long long ll;
#define st first
#define nd second
  vector<int> get_primes(int n){
    vector<bool> b(n+1);
    vector<int> p;
    for(int i=2;i<=n;i++){
      if(!b[i])p.emplace_back(i);
      for(int j:p){
        if(1ll*i*j>n)break;
        b[i*j]=true;
        if(!(i%j))break;
      }
    }
    return p;
  }
  inline ll safe_mulll(ll a,ll b,ll mod){
    ll r=0;
    while(b){
      if(b&1)(r+=a)%=mod;
      (a<<=1)%=mod; b>>=1;
    }
    return r;
  }
  inline int pow_mod(int a,int b,int mod){
    int r=1;
    while(b){
      if(b&1)r=r%mod*a%mod;
      a=a%mod*a%mod; b>>=1;
    }
    return r;
  }
  inline ll pow_modll(ll a,ll b,ll mod){
    ll r=1;
    while(b){
      if(b&1)r=r%mod*a%mod;
      a=a%mod*a%mod; b>>=1;
    }
    return r;
  }
  inline int inv_p(int x,int mod){
    return pow_mod(x,mod-2,mod);
  }
  inline ll inv_pll(ll x,ll mod){
    return pow_modll(x,mod-2,mod);
  }
  pair<int,int> exgcd(int a,int b){
    if(!b)return make_pair(1,0);
    auto [x,y]=exgcd(b,a%b);
    int t=x; x=y; y=t-a/b*y;
    return make_pair(x,y);
  }
  pair<ll,ll> exgcdll(ll a,ll b){
    if(!b)return make_pair(1,0);
    auto [x,y]=exgcdll(b,a%b);
    ll t=x; x=y; y=t-a/b*y;
    return make_pair(x,y);
  }
  inline int inv_cp(int x,int mod){
    if(gcd(x,mod)>1)return -1;
    return (exgcd(x,mod).st%mod+mod)%mod;
  }
  inline ll inv_cpll(ll x,ll mod){
    if(gcd(x,mod)>1)return -1;
    return (exgcdll(x,mod).st%mod+mod)%mod;
  }
  inline ll crt(vector<pair<ll,ll> > a){
    ll p=1,s=0;
    for(auto [r,m]:a)p*=m;
    for(auto [r,m]:a){
      ll m2=p/m,i=inv_cpll(m2,m);
      s+=r*m2*i;
    }
    return s;
  }
  inline ll crt_mod(vector<pair<ll,ll> > a,ll mod){
    ll p=1,s=0;
    for(auto [r,m]:a)p*=m;
    for(auto [r,m]:a){
      ll m2=p/m,i=inv_cpll(m2,m);
      (s+=r*m2%mod*i%mod)%=mod;
    }
    return s;
  }
  inline double lagrange(vector<pair<int,int> > a,int k){
    double c=0;
    for(int i=0;i<a.size();i++){
      double s1=a[i].nd;
      for(int j=0;j<a.size();j++)
        if(i!=j)s1*=1.0*(k-a[j].st)/(a[i].st-a[j].st);
      c+=s1;
    }
    return c;
  }
  inline long double lagrange(vector<pair<ll,ll> > a,ll k){
    long double c=0;
    for(int i=0;i<a.size();i++){
      long double s1=a[i].nd;
      for(int j=0;j<a.size();j++)
        if(i!=j)s1*=1.0*(k-a[j].st)/(a[i].st-a[j].st);
      c+=s1;
    }
    return c;
  }
  inline int lagrange_mod(vector<pair<int,int> > a,int k,int mod){
    int c=0;
    for(int i=0;i<a.size();i++){
      int s1=a[i].nd%mod,s2=1;
      for(int j=0;j<a.size();j++)
        if(i!=j)s1=s1*(k-a[j].st)%mod,
          s2=s2*(a[i].st-a[j].st)%mod;
      (c+=s1*inv_cp((s2%mod+mod)%mod,mod)%mod+mod)%=mod;
    }
    return c;
  }
  inline ll lagrange_modll(vector<pair<ll,ll> > a,ll k,ll mod){
    ll c=0;
    for(int i=0;i<a.size();i++){
      ll s1=a[i].nd%mod,s2=1;
      for(int j=0;j<a.size();j++)
        if(i!=j)s1=s1*(k-a[j].st)%mod,
          s2=s2*(a[i].st-a[j].st)%mod;
      (c+=s1*inv_cpll((s2%mod+mod)%mod,mod)%mod+mod)%=mod;
    }
    return c;
  }
#undef st
#undef nd
}

功能介绍

• vector<int> get_primes(int n)：查找 [2,n](2\le n\le 10^8) 以内的所有质数，并返回包含它们的一个数组（std::vector），时间复杂度 O(n)；
• long long safe_mulll(long long a,long long b,long long mod)：返回 a\times b\bmod mod(0\le a,b\le 10^{18},1\le mod\le 10^{18}) 的值，时间复杂度 O(\log b)；
• int pow_mod(int a,int b,int mod) / long long pow_modll(long long a,long long n,long long mod)：返回 a^b\bmod mod(0\le a,b\le 10^{9},1\le mod\le 10^{9}) 的值，时间复杂度 O(\log b)；
• int inv_p(int x,int mod) / long long inv_pll(long long x,long long mod)：返回 x(1\le x<mod) 在模 mod(1\le mod\le 10^9)（mod 是质数）意义下的逆元，时间复杂度 O(\log mod)；
• pair<int,int> exgcd(int a,int b)：返回关于 x,y 的不定方程 ax+by=1 的解 (x,y)，时间复杂度 O(\log\max(a,b))；
• int inv_cp(int x,int mod) / long long inv_cpll(long long x,long long mod)：返回 x(1\le x<mod) 在模 mod(1\le mod\le 10^9)（mod 不一定是质数）意义下的逆元，如果 x 没有逆元返回 -1，时间复杂度 O(\log mod)；
• long long crt(vector<pair<long long,long long> > a) / long long crt_mod(vector<pair<long long,long long> > a,int mod)：返回满足 \forall1\le i,j\le n\land i\ne j,m_i\perp m_j 的方程组 \begin{cases} x\equiv r_0\pmod {m_0}\\ x\equiv r_1\pmod {m_1}\\ \vdots\\ x\equiv r_{n-1}\pmod {m_{n-1}}\\ \end{cases}

  的最小非负整数解 x，时间复杂度 O(n\log\max\{m_i\})。可选择是否将 x 对某个数 mod 取模；

• double lagrange(vector<pair<int,int> > a,int k) / long double lagrange(vector<pair<long long,long long> > a,long long k)：通过其在若干个点上的值确定一个多项式 f(x) 并求出 f(k)，时间复杂度 O(n^2)，这里 n 是 a 的大小，即给出的点的个数；
• int lagrange_mod(vector<pair<int,int> > a,int k,int mod) / long long lagrange_modll(vector<pair<long long,long long> > a,long long k,long long mod)：同上，求出 f(k)\bmod mod，时间复杂度 O(n^2)。

示例代码

P2480 古代猪文 by FFTotoro

第二部分 普通模板

警告：该部分模板未经过大量的实践测试，可能存在一定错误。请谨慎使用。

数据结构（Data Structure）

离散化（Discretization）

namespace IAOI_lib{
  vector<int> discretization(vector<int> a){
    auto b=a; sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    for(auto &i:a)i=lower_bound(b.begin(),b.end(),i)-b.begin();
    return a;
  }
}

线性代数（Linear Algebra）

矩阵（Matrix）

包含：矩阵转置（Transpose）、矩阵的秩（Rank）和行列式求值（Determinant）。

namespace IAOI_lib{
  typedef long long ll;
  inline vector<vector<ll> > trans(vector<vector<ll> > a){
    vector b(a[0].size(),vector<ll>(a.size()));
    for(int i=0;i<a.size();i++)
      for(int j=0;j<a[0].size();j++)
        b[j][i]=a[i][j];
    return b;
  }
  inline int rank(vector<vector<ll> > a,const int &p){
    auto pow_mod=[&](ll a,ll b){
      ll r=1;
      while(b){
        if(b&1)(r*=a)%=p;
        (a*=a)%=p,b>>=1;
      }
      return r;
    };
    if(a.empty()||a[0].empty())return 0;
    if(a.size()>a[0].size())a=trans(a);
    int r=0;
    for(int i=0;i<a.size();i++){
      for(int j=i;j<a[0].size();j++)
        if(a[i][j]){
          if(i!=j){
            for(int k=i;k<a.size();k++)
              swap(a[k][i],a[k][j]);
          }
          break;
        }
      if(!a[i][i])continue;
      int x=pow_mod(a[i][i],p-2);
      for(int j=i+1;j<a.size();j++)
        if(a[j][i]){
          int d=a[j][i]*x%p;
          for(int k=i;k<a[0].size();k++)
            (a[j][k]+=p-a[i][k]*d)%=p;
        }
      r++;
    }
    return r;
  }
  inline ll det(vector<vector<ll> > a,const int &p){
    ll s=1;
    for(int i=0;i<a.size();i++)
      for(int j=i+1;j<a.size();j++){
        while(a[i][i]){
          ll d=a[j][i]/a[i][i];
          for(int k=i;k<a.size();k++)
            (a[j][k]+=p-a[i][k]*d%p)%=p;
          swap(a[i],a[j]),s=-s;
        }
        swap(a[i],a[j]),s=-s;
      }
    for(int i=0;i<a.size();i++)
      (s*=a[i][i])%=p;
    return (s+p)%p;
  }
}

异或线性基（XOR Basis）

namespace IAOI_lib{
  typedef long long ll;
  class linear_basis{
    private:
      vector<ll> a;
    public:
      linear_basis(int b){
        a.resize(b);
      }
      inline void insert(ll x){
        for(int i=a.size()-1;~i;i--)
          if(x>>i&1){
            if(a[i])x^=a[i];
            else{a[i]=x; break;}
          }
      }
      inline ll query(){
        ll c=0;
        for(int i=a.size()-1;~i;i--)
          c=max(c,c^a[i]);
        return c;
      }
      inline void merge(LinearBasis x){
        assert(a.size()==x.a.size());
        for(int i=a.size()-1;~i;i--)
          this->insert(x.a[i]);
      }
  };
}

图论（Graph Theory）

2-满足性问题（2-SAT）

注意该模板输入为 1-indexed（按照 CNF 格式输入），返回值为 0-indexed。

namespace IAOI_lib{
  variant<vector<bool>,bool> twosat(int n,vector<pair<int,int> > e){
    vector<vector<int> > g(n<<1);
    for(auto &[u,v]:e){
      if(u<0)u=n-u; if(v<0)v=n-v;
      g[(u>n?u-n:u+n)-1].emplace_back(v-1);
      g[(v>n?v-n:v+n)-1].emplace_back(u-1);
    }
    int o=0,r=-1;
    vector<int> d(n<<1,-1),l(n<<1),c(n<<1,-1);
    stack<int> s;
    function<void(int)> tarjan=[&](int u){
      d[u]=l[u]=o++,s.emplace(u);
      for(int i:g[u])
        if(d[i]<0)tarjan(i),l[u]=min(l[u],l[i]);
        else if(c[i]<0)l[u]=min(l[u],d[i]);
      if(d[u]==l[u]){
        r++; while(s.top()!=u)
          c[s.top()]=r,s.pop();
        c[u]=r,s.pop();
      }
    };
    for(int i=0;i<n<<1;i++)
      if(d[i]<0)tarjan(i);
    for(int i=0;i<n;i++)
      if(c[i]==c[i+n])return false;
    vector<bool> b(n);
    for(int i=0;i<n;i++)
      b[i]=c[i]<c[i+n];
    return b;
  }
}

一般图最大匹配（Blossom）

namespace IAOI_lib{
  class matching{
    private:
      int n,c;
      vector<vector<int> > g;
      vector<int> o,p,pr,w,f;
      int leader(int x){
        return x==f[x]?x:f[x]=leader(f[x]);
      }
      inline int lca(int u,int v){
        c++,u=leader(u),v=leader(v);
        while(o[u]!=c){
          o[u]=c,u=leader(pr[p[u]]);
          if(v<n)swap(u,v);
        }
        return u;
      }
      void augment(int u){
        if(u<n)augment(p[pr[u]]),p[p[u]=pr[u]]=u;
      }
      bool blossom(int u){
        fill(pr.begin(),pr.end(),n);
        fill(w.begin(),w.end(),n);
        iota(f.begin(),f.end(),0);
        queue<int> q; q.emplace(u),w[u]=1;
        auto shrink=[&](int u,int v,int a){
          while(leader(u)!=a){
            pr[u]=v,v=p[u],f[u]=f[v]=a,u=pr[v];
            if(!w[v])w[v]=1,q.emplace(v);
          }
        };
        while(!q.empty()){
          int u=q.front(); q.pop();
          for(int i:g[u]){
            if(leader(u)==leader(i))continue;
            if(w[i]==1){
              int a=lca(u,i);
              shrink(u,i,a),shrink(i,u,a);
            }
            if(w[i]==n){
              pr[i]=u,w[i]=0;
              if(p[i]<n)w[p[i]]=1,q.emplace(p[i]);
              else{augment(i); return true;}
            }
          }
        }
        return false;
      }
    public:
      matching(int n_){
        c=0,g.resize(n=n_),p.resize(n+1,n);
        pr.resize(n+1),w.resize(n+1);
        o.resize(n+1),f.resize(n+1);
      }
      inline void add_edge(int u,int v){
        g[u].emplace_back(v);
        g[v].emplace_back(u);
      }
      pair<int,vector<pii> > solve(){
        int s=0; vector<pii> v;
        for(int i=0;i<n;i++)
          if(p[i]==n)s+=blossom(i);
        for(int i=0;i<n;i++)
          if(p[i]<i)v.emplace_back(p[i],i);
        return make_pair(s,v);
      }
  };
}

二分图边染色（Vizing）

namespace IAOI_lib{
  class bipar_edge_coloring{
    private:
      vector<int> d;
      vector<vector<int> > a;
    public:
      bipar_edge_coloring(int n,int m){
        d.resize(n+m);
        a.resize(n+m,vector<int>(n+m,-1));
      }
      inline int add_edge(int u,int v){
        d[u]++,d[v]++;
        int c1=0,c2=0;
        while(~a[u][c1])c1++;
        while(~a[v][c2])c2++;
        a[u][c1]=v,a[v][c2]=u;
        if(c1!=c2)
          for(int c3=c2,i=v;~i;i=a[i][c3],c3^=c1^c2)
            swap(a[i][c1],a[i][c2]);
        return c1;
      }
      pair<int,vector<vector<int> > > color(){
        return make_pair(*max_element(d.begin(),d.end()),a);
      }
  };
}

无向图带权三元环计数（Enumerate Triangles）

namespace IAOI_lib{
  typedef long long ll;
  ll enumerate_triangles(vector<int> x,vector<vector<int> > g){
    int n=g.size(); ll c=0;
    vector<vector<int> > g2(n);
    for(int u=0;u<n;u++)
      for(int v:g[u])
        if(make_pair(g[u].size(),u)>make_pair(g[v].size(),v))
          g2[v].emplace_back(u);
    vector<int> b(n,-1);
    for(int u=0;u<n;u++){
      for(int v:g2[u])b[v]=u;
      for(int v:g2[u])
        for(int i:g2[v])
          if(b[i]==u)c+=1ll*x[u]*x[v]*x[i];
    }
    return c;
  }
  int enumerate_triangles_mod(vector<int> x,vector<vector<int> > g,const int p){
    auto add=[&](int &x,int y){
      if((x+=y)>=p)x-=p;
    };
    int n=g.size(),c=0;
    vector<vector<int> > g2(n);
    for(int u=0;u<n;u++)
      for(int v:g[u])
        if(make_pair(g[u].size(),u)>make_pair(g[v].size(),v))
          g2[v].emplace_back(u);
    vector<int> b(n,-1);
    for(int u=0;u<n;u++){
      for(int v:g2[u])b[v]=u;
      for(int v:g2[u])
        for(int i:g2[v])
          if(b[i]==u)add(c,1ll*x[u]*x[v]%p*x[i]%p);
    }
    return c;
  }
}

卷积

按位与 / 或 / 异或卷积（Bitwise AND / OR / XOR Convolution Mod 998244353）

namespace IAOI_lib{
  typedef long long ll;
  typedef vector<int> poly;
  const int p=998244353;
  namespace internal{
    inline int add(int x,int y){
      int s=x+y; if(s>=p)s-=p; return s;
    }
    inline void chadd(int &x,int y){
      if((x+=y)>=p)x-=p;
    }
    inline poly mul(poly a,poly b){
      poly s(a.size());
      for(int i=0;i<a.size();i++)
        s[i]=(ll)a[i]*b[i]%p;
      return s;
    }
    inline poly and_fwt(int n,poly a,int x){
      auto b=a; chadd(x,p);
      for(int i=0;i<n;i++)
        for(int j=0;j<a.size();j+=1<<i+1)
          for(int k=0;k<1<<i;k++)
            chadd(b[j|k],(ll)b[j|1<<i|k]*x%p);
      return b;
    }
    inline poly or_fwt(int n,poly a,int x){
      auto b=a; chadd(x,p);
      for(int i=0;i<n;i++)
        for(int j=0;j<a.size();j+=1<<i+1)
          for(int k=0;k<1<<i;k++)
            chadd(b[j|1<<i|k],(ll)b[j|k]*x%p);
      return b;
    }
    inline poly xor_fwt(int n,poly a,int x){
      auto b=a; chadd(x,p);
      for(int i=0;i<n;i++)
        for(int j=0;j<a.size();j+=1<<i+1)
          for(int k=0;k<1<<i;k++){
            int u=(ll)add(b[j|k],b[j|1<<i|k])*x%p,
              v=(ll)add(b[j|k],p-b[j|1<<i|k])*x%p;
            b[j|k]=u,b[j|1<<i|k]=v;
          }
      return b;
    }
  }
  inline poly and_convolution(poly a,poly b){
    int n=__lg(a.size());
    return internal::and_fwt(n,internal::mul(internal::and_fwt(n,a,1),internal::and_fwt(n,b,1)),-1);
  }
  inline poly or_convolution(poly a,poly b){
    int n=__lg(a.size());
    return internal::or_fwt(n,internal::mul(internal::or_fwt(n,a,1),internal::or_fwt(n,b,1)),-1);
  }
  inline poly xor_convolution(poly a,poly b){
    int n=__lg(a.size());
    return internal::xor_fwt(n,internal::mul(internal::xor_fwt(n,a,1),internal::xor_fwt(n,b,1)),p+1>>1);
  }
}

普通卷积（Convolution Mod 998244353）

警告：使用 pow 函数时需要保证 x_0=1。

namespace IAOI_lib{
  typedef long long ll;
  typedef vector<int> poly;
  const int g=3,ng=332748118,p=998244353;
  namespace internal{
    inline int add(int x,int y){
      int s=x+y; if(s>=p)s-=p; return s;
    }
    inline void chadd(int &x,int y){
      if((x+=y)>=p)x-=p;
    }
    inline int qpow(int a,int b){
      int r=1;
      while(b){
        if(b&1)r=1ll*r*a%p;
        a=1ll*a*a%p,b>>=1;
      }
      return r;
    }
    inline void ntt(poly &a,int l,int op){
      poly r(l);
      for(int i=1;i<l;i++)
        r[i]=(r[i>>1]>>1)|(i&1?l>>1:0);
      for(int i=0;i<l;i++)
        if(i<r[i])swap(a[i],a[r[i]]);
      for(int i=2;i<=l;i<<=1){
        int k=qpow(op>0?g:ng,(p-1)/i);
        vector<int> q(i>>1);
        for(int j=q[0]=1;j<i>>1;j++)
          q[j]=(ll)q[j-1]*k%p;
        for(int j=0;j<l;j+=i)
          for(int k=j;k<j+(i>>1);k++){
            int x=a[k],y=(ll)q[k-j]*a[k+(i>>1)]%p;
            chadd(a[k],y),a[k+(i>>1)]=add(x,p-y);
          }
      }
      if(op<0){
        int I=internal::qpow(l,p-2);
        for(int i=0;i<l;i++)
          a[i]=(ll)a[i]*I%p;
      }
    }
  }
  inline poly convolution(poly x,poly y){
    int l=1,n=x.size()+y.size();
    while(l<n<<1)l<<=1;
    while(x.size()<l)x.emplace_back(0);
    while(y.size()<l)y.emplace_back(0);
    internal::ntt(x,l,1),internal::ntt(y,l,1);
    for(int i=0;i<l;i++)
      x[i]=(ll)x[i]*y[i]%p;
    internal::ntt(x,l,-1);
    return poly(x.begin(),x.begin()+n-1);
  }
  inline poly operator *(const poly &x,const poly &y){
    return convolution(x,y);
  }
  inline poly operator *=(poly &x,const poly &y){
    return x=convolution(x,y);
  }
  inline poly pow(poly x,ll k){
    int n=x.size(),l=1;
    while(l<n<<1)l<<=1;
    while(x.size()<l)x.emplace_back(0);
    vector<int> r(l); r[0]=1;
    internal::ntt(r,l,1),internal::ntt(x,l,1);
    while(k){
      if(k&1){
        for(int i=0;i<l;i++)
          r[i]=(ll)r[i]*x[i]%p;
        internal::ntt(r,l,-1);
        fill(r.begin()+n,r.begin()+l,0);
        internal::ntt(r,l,1);
      }
      for(int i=0;i<l;i++)
        x[i]=(ll)x[i]*x[i]%p;
      internal::ntt(x,l,-1);
      fill(x.begin()+n,x.begin()+l,0);
      internal::ntt(x,l,1),k>>=1;
    }
    internal::ntt(r,l,-1);
    return poly(r.begin(),r.begin()+n);
  }
}

第三部分 命题相关模板

简单子任务配置生成器

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cout<<"Number of subtasks: ";
  int n; cin>>n;
  vector<int> a(n),s(n);
  for(int i=0;i<n;i++){
    cout<<"Number of testcases in subtask "<<i<<": ",cin>>a[i];
    cout<<"Score of subtask "<<i<<": ",cin>>s[i];
  }
  cout<<"Time Limit (ms): ";
  int tl; cin>>tl;
  cout<<"Memory Limit (MB): ";
  int ml; cin>>ml;
  freopen("config.yml","w",stdout);
  for(int i=0;i<n;i++){
    for(int j=0;j<a[i];j++){
      cout<<setfill('0')<<setw(2)<<i+1<<'-'<<setfill('0')<<setw(2)<<j+1<<".in: \n";
      cout<<"  timeLimit: "<<tl<<'\n';
      cout<<"  memoryLimit: "<<(ml<<10)<<'\n';
      cout<<"  score: "<<s[i]<<'\n';
      cout<<"  subtaskId: "<<i<<'\n'<<endl;
    }
  }
  return 0;
}