一些神奇の小公式

• $n$ 以内的质数个数为 ：

  ​ $n/\log n*\sqrt{n}$

• $n$ 个点的距离平方和：

  ​ $n*(\sum x_i+\sum y_i)-[(\sum x_i)^2+(\sum y_i)^2]$

一些神奇の板子

万年不变

万能（火车）头

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<string>
#include<vector>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll; 
const int N,M,INF=1e9,MIN=-1e9,mo;

图论板子

链式前向星

struct no{
    int to,v;
}node[M];
int head[N],idx=0;
void add(int u,int v){
    idx++;
    node[idx].v=v;
    node[idx].to=head[u];
    head[u]=idx;
}

并查集

int f[N];
void init(int n){
    for(int i=1;i<=n;i++)
    f[i]=i;
    return;
}
int find(int u){
    if(f[u]!=u)
    f[u]=find(f[u]);
    return f[u];
}
void hb(int u,int v){
    int fu=find(u),fv=find(v);
    if(fu!=fv){
        f[fv]=fu;
    }
    return;
}

$dinic$ 算法

需定义 $n$ ， $S$ ， $T$

struct no{
	int v,to,f;
}node[M];
int head[N],idx=1;
void add(int u,int v,int f){
	idx++;
	node[idx].v=v;
	node[idx].f=f;
	node[idx].to=head[u];
	head[u]=idx;
	idx++;
	node[idx].v=u;
	node[idx].f=0;
	node[idx].to=head[v];
	head[v]=idx;
	return;
}
int q[N],d[N],cur[N];
bool bfs(){
	memset(d,-1,sizeof(d));
	int h=0,t=0;
	q[0]=S,d[S]=0;
	cur[S]=head[S];
	while(h<=t){
		int u=q[h++];
		for(int i=head[u];i;i=node[i].to){
			int v=node[i].v;
			if(d[v]==-1&&node[i].f){
				d[v]=d[u]+1;
				if(v==T)
				return 1;
				cur[v]=head[v];
				q[++t]=v;
			}
		}
	}
	return 0;
}
int find(int u,int limit){
	if(u==T)
	return limit;
	int flow=0;
	for(int i=cur[u];i&&flow<limit;i=node[i].to){
		int v=node[i].v;
		cur[u]=i;
		if(d[v]==d[u]+1&&node[i].f){
			int t=find(v,min(node[i].f,limit-flow));
			if(!t)
			d[v]=-1;
			node[i].f-=t;
			node[i^1].f+=t;
			flow+=t;
		}
	}
	return flow;
}
int dinic(){
	int r=0,flow;
	while(bfs()){
		while(flow=find(S,INF))
		r+=flow;
	}
	return r;
}

数论板子

$kasumi$ （快速幂）

ll POW(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1)
        res*=x;
        y>>=1;
        x*=x;
    }
    return res;
}

辗转相除 $gcd$

ll gcd(ll x,ll y){
	ll r=x%y;
	while(r){
		x=y;
		y=r;
		r=x%y;
	}
	return y;
}

优化时间板子

快读

ll read(){
    ll res=0,f=1;
    char _z=getchar();
    while(_z<'0'||_z>'9'){
        if(_z=='-')
        break;
        _z=getchar();
    }
    if(_z=='-'){
        _z=getchar();
        f=-1;
    }
    while(_z>='0'&&_z<='9'){
        res=(res<<3)+(res<<1)+_z-'0';
        _z=getchar();
    }
    return res*f;
}

快输

void putout(ll x){
    if(x>9)
    putout(x/10);
    putchar(x%10+'0');
    return;
}

树状数组

int n;		//数的个数 
int c[N];	//前缀和 
int lowbit(int x){
	return x&-x;
}
void add(int x,int y){	//在x的位置加上y 
	for(int i=x;i<=n;i+=lowbit(i)){
		c[i]+=y;
	}
	return;
}
int qu(int x){	//查询[1,x]的数的和 
	int res=0;
	for(int i=x;i>0;i-=lowbit(i)){
		res+=c[i];
	}
	return res;
}