一些神奇の小公式
-
$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;
}