数学

组合数

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;

/*求组合数*/
LL ksm(LL a,LL b,LL mod)
{
    LL res=1,base=a;
    while(b)
    {
        if(b&1)res=(res*base)%mod;
        base=(base*base)%mod;
        b>>=1;
    }
    return res;
}

LL fac[maxn]= {1,1},invf[maxn]= {1,1},inv[maxn]= {1,1};
void InitFac(int n)
{
    for(int i=2; i<=n; i++)
    {
        fac[i]=fac[i-1]*i%MOD; //阶乘
        inv[i]=((MOD-MOD/i)*inv[MOD%i])%MOD;//逆元线性筛 
    }
    invf[n]=ksm(fac[n],MOD-2,MOD);
    for(int i=n-1; i>=2; i--)invf[i]= invf[i+1]*(i+1)%MOD; //阶乘逆元线性筛

}

各种线性筛


#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
/*各种线性筛*/
bool vis[maxn];
LL phi[maxn],mu[maxn],Smu[maxn];//欧拉函数，莫比乌斯函数，莫比乌斯函数前缀和 
vector<int>prime;//存质数 
void PHI(int n)
{
    memset(vis,1,sizeof(vis));
    phi[1]=1;
    mu[1]=1;
    Smu[1]=1;
    for(int i=2; i<=n; i++)
    {
        if(vis[i])
        {
            prime.push_back(i);
            phi[i]=i-1;
            mu[i]=-1;
        }
        for(int j=0; j<prime.size()&&i*prime[j]<=n; j++)
        {
            vis[i*prime[j]]=0;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                mu[i*prime[j]]=0;
                break;
            }
            else
            {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
                mu[i*prime[j]]=-mu[i];
            }
        }
        Smu[i]=Smu[i-1]+mu[i];
    }
}

图论

邻接表

struct Edge
{
    int t,v,nxt;
};
Edge E[maxn];
int head[maxn];
int tot;
void AddEdge(int aa,int bb,int val)
{
    E[++tot].t=bb;
    E[tot].v=val;
    E[tot].nxt=head[aa];
    head[aa]=tot;
}