来自Luogu神犇的数学学习笔记——https://www.luogu.com.cn/article/ubd4ucn3

$\texttt{My tools}$

$\texttt{Phigros rks 14.76}$

开歌名

Phira 密码：73ac

something nice come from Luogu

Touch/Click to play!

你已进入雷区！请时刻留意身后！

Bellman-Ford 最短路算法

可以通过 Luogu P3371 【模板】单源最短路径（弱化版）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int N=1e4+5,INF=0x3f3f3f3f;
struct edge{int t,w;};
int n,m,u,v,w,dis[N],st;
vector<edge>g[N];
void bellmanford(int u){
	memset(dis,127,sizeof(dis));
	dis[u]=0;
	bool isrelex=true;
	while(isrelex){
		isrelex=false;
		for(int s=1;s<=n;s++){
			for(size_t i=0;i<g[s].size();i++){
				int t=g[s][i].t,w=g[s][i].w;
				if(dis[t]>dis[s]+w){
					dis[t]=dis[s]+w;
					isrelex=true;
				}
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&st);
	while(m--){
		scanf("%d%d%d",&u,&v,&w);
		g[u].push_back({v,w});
	}
	bellmanford(st);
	for(int i=1;i<=n;i++){
		if(dis[i]==dis[0])printf("%d ",(1ll<<31)-1);
		else printf("%d ",dis[i]);
	}
	return 0;
}

SPFA（Bellman-Ford 队列优化）

关于 SPFA，它死了。

请谨慎使用 SPFA！最坏时间复杂度仍为 $\mathcal{O}(VE)$ 且易卡！

可以通过 Luogu P3371 【模板】单源最短路径（弱化版）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int N=1e4+5,INF=0x3f3f3f3f;
struct edge{int t,w;};
int n,m,u,v,w,dis[N],st;
vector<edge>g[N];
bool vis[N];
queue<int>que;
void spfa(int u){
	memset(dis,127,sizeof(dis));
	dis[u]=0,vis[u]=true;
	que.push(u);
	while(!que.empty()){
		int s=que.front();
		que.pop();
		vis[s]=false;
		for(edge e:g[s]){
			if(dis[e.t]>dis[s]+e.w){
				dis[e.t]=dis[s]+e.w;
				if(!vis[e.t]){
					que.push(e.t);
					vis[e.t];
				}
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&st);
	while(m--){
		scanf("%d%d%d",&u,&v,&w);
		g[u].push_back({v,w});
	}
	spfa(st);
	for(int i=1;i<=n;i++){
		if(dis[i]==dis[0])printf("%d ",(1ll<<31)-1);
		else printf("%d ",dis[i]);
	}
	return 0;
}

快速幂

#include<cstdio>
#define ll long long
using namespace std;
ll fastPow(ll b,ll p,ll mod){
	//b%=mod [{mod} is a Prime]
	ll res=1;
	while(p>0){
		if(p&1)res=res*b%mod;
		b=b*b%mod,p>>=1;
	}
	return res;
}

树状数组

单点更改，范围查询

template<typename T,const int SIZE>
class treeArray{
private:
	T tree[SIZE];
	int lowbit(int x){return x&-x;}
	T query(int p){T sum=0;while(p>0){sum+=tree[p];p-=lowbit(p);}return sum;}
public:
	void update(int p,T val){while(p<=SIZE){tree[p]+=val;p+=lowbit(p);}}
	T range(int lb,int ub){return query(ub)-query(lb-1);}
};

多点更改，多点查询

template<typename T,const int SIZE>
class treeArray{
private:
	T tree1[SIZE],tree2[SIZE];
	int lowbit(int x){return x&-x;}
	void upd(T tr[],int p,T val){while(p<=SIZE){tr[p]+=val;p+=lowbit(p);}}
	int qry(T tr[],int p){T sum=0;while(p>0){sum+=tr[p];p-=lowbit(p);}return sum;}
public:
	void update(int l,int r,T val){
		upd(tree1,l,val);upd(tree1,r+1,-val);
		upd(tree2,l,(l-1)*val);upd(tree2,r+1,-(r*val));
	}
	T range(int l,int r){
		return qry(tree1,r)*r-qry(tree2,r)-qry(tree1,l-1)*(l-1)+qry(tree2,l-1);
	}
};

优先队列（小根/大根堆）

template<typename T,unsigned int siz,bool(*cmp)(T x,T y)>
class pri_queue{
private:
	int len=0;
	T heap[siz];
	void swap(T &a,T &b){T tmp=a;a=b;b=tmp;}
	void push_up(int x){
		while(x>1&&cmp(heap[x>>1],heap[x])){
			swap(heap[x>>1],heap[x]);
			x>>=1;
		}
	}
	void push_down(int x){
		int p=1,l,r;
		while(true){
			l=x<<1,r=(x<<1)+1;
			if(l<=len&&cmp(heap[x],heap[l]))p=l;
			if(r<=len&&cmp(heap[p],heap[r]))p=r;
			if(x==p)return;
			else{
				swap(heap[x],heap[p]);
				x=p;
			}
		}
	}
public:
	T* begin(){return heap+1;}
	T* end(){return heap+len+1;}
	int size(){return len;}
	bool empty(){return len==0;}
	T top(){return heap[1];}
	void push(T val){
		heap[++len]=val;
		push_up(len);
	}
	void pop(){
		heap[1]=heap[len--];
		push_down(1);
	}
};
bool cmp(int a,int b){return a<b;}//小根堆

高精度计算

高精度

#include<iostream>
#include<vector>
#include<cstring>
#include<cassert>
#define ll long long
using namespace std;
struct BigInteger{
	static const ll BASE=100000000;
	static const ll WIDTH=8;
	vector<ll>s;
	BigInteger&clean(){while(!s.back()&&s.size()>1)s.pop_back();return*this;}
	BigInteger(ll num=0){*this=num;}
	BigInteger(string s){*this=s;}
	BigInteger&operator=(ll num){s.clear();do{s.push_back(num%BASE);num/=BASE;}while(num>0);return*this;}
	BigInteger&operator=(const string&str){s.clear();ll x,len=(str.length()-1)/WIDTH+1;for(ll i=0;i<len;i++){ll end=str.length()-i*WIDTH;ll start=max(0ll,end-WIDTH);sscanf(str.substr(start,end-start).c_str(),"%lld",&x);s.push_back(x);}return(*this).clean();}
	BigInteger operator+(const BigInteger&b)const{BigInteger c;c.s.clear();for(size_t i=0,g=0;;i++){if(g==0&&i>=s.size()&&i>=b.s.size())break;ll x=g;if(i<s.size())x+=s[i];if(i<b.s.size())x+=b.s[i];c.s.push_back(x%BASE);g=x/BASE;}return c;}
	BigInteger operator-(const BigInteger&b)const{assert(b<=*this);BigInteger c;c.s.clear();for(size_t i=0,g=0;;i++){if(g==0&&i>=s.size()&&i>=b.s.size())break;ll x=s[i]+g;if(i<b.s.size())x-=b.s[i];if(x<0)g=-1,x+=BASE;else g=0;c.s.push_back(x);}return c.clean();}
	BigInteger operator*(const BigInteger&b)const{ll g;vector<ll>v(s.size()+b.s.size(),0);BigInteger c;c.s.clear();for(size_t i=0;i<s.size();i++)for(ll j=0;j<b.s.size();j++)v[i+j]+=(ll)(s[i])*b.s[j];for(ll i=0,g=0;;i++){if(g==0&&i>=v.size())break;ll x=v[i]+g;c.s.push_back(x%BASE);g=x/BASE;}return c.clean();}
	BigInteger operator/(const BigInteger&b)const{assert(b>0);BigInteger c=*this;BigInteger m;for(ll i=s.size()-1;i>=0;i--){m=m*BASE+s[i];c.s[i]=bsearch(b,m);m-=b*c.s[i];}return c.clean();}
	BigInteger operator%(const BigInteger&b)const{BigInteger c=*this;BigInteger m;for(ll i=s.size()-1;i>=0;i--){m=m*BASE+s[i];c.s[i]=bsearch(b, m);m-=b*c.s[i];}return m;}
	ll bsearch(const BigInteger&b,const BigInteger&m)const{ll L=0,R=BASE-1,x;while(true){x=(L+R)>>1;if(b*x<=m){if(b*(x+1)>m)return x;else L=x;}else R=x;}}
	BigInteger&operator+=(const BigInteger&b){*this=*this+b;return*this;}
	BigInteger&operator-=(const BigInteger&b){*this=*this-b;return*this;}
	BigInteger&operator*=(const BigInteger&b){*this=*this*b;return*this;}
	BigInteger&operator/=(const BigInteger&b){*this=*this/b;return*this;}
	BigInteger&operator%=(const BigInteger&b){*this=*this%b;return*this;}
	bool operator<(const BigInteger&b)const{if(s.size()!=b.s.size()){return s.size()<b.s.size();}for(ll i=s.size()-1;i>=0;i--)if(s[i]!=b.s[i])return s[i]<b.s[i];return false;}
	bool operator>(const BigInteger&b)const{return b<*this;}
	bool operator<=(const BigInteger&b)const{return!(b<*this);}
	bool operator>=(const BigInteger&b)const{return!(*this<b);}
	bool operator!=(const BigInteger&b)const{return b<*this||*this<b;}
	bool operator==(const BigInteger&b)const{return!(b<*this)&&!(b>*this);}
};
ostream&operator<<(ostream&out,const BigInteger&x){out<<x.s.back();for(ll i=x.s.size()-2;i>=0;i--){char buf[20];sprintf(buf,"%08lld",x.s[i]);for(size_t j=0;j<strlen(buf);j++){out<<buf[j];}}return out;}
istream&operator>>(istream&in,BigInteger&x){string s;if(!(in>>s))return in;x=s;return in;}
BigInteger binpow(BigInteger b,BigInteger p,BigInteger m){
	//b%=m {m is a prime.}
	BigInteger ans=1;
	while(p>0){
		if(p%2==1)ans=ans*b%m;
		b=b*b%m;
		p/=2;
	}
	return ans;
}
BigInteger Math_C(BigInteger n,BigInteger k){
	if(k==0||k==n)return 1;
	BigInteger ans=1;
	for(BigInteger i=k+1;i<=n;i+=1)ans*=i;
	for(BigInteger i=2;i<=n-k;i+=1)ans/=i;
	return ans;
}
BigInteger Math_P(BigInteger n,BigInteger k){
	BigInteger ans=1;
	for(BigInteger i=n-k+1;i<=n;i+=1)ans*=i;
	return ans;
}

FFT优化

原版

压行

对拍

#include<cstdio>
#include<cstdlib>
int main(){
	while(true){
		system("gen > test.in");
		system("test1.exe < test.in > a.out");
		system("test2.exe < test.in > b.out");
		if(system("fc a.out b.out")){
			system("pause");
			return 0;
		}
	}
}