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

$\texttt{My tools}$

小熊猫 IDE 密码 $\text{f0tp}$

$\texttt{Phigros rks 15.00!!!}$

开歌名

Phira 密码：73ac

something nice come from Luogu

v/s 攻略

Touch/Click to play!

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

更新说明

2025/8/22

确认了树状数组模板的正确性，更新了线段树（模板正在封装中，已 AC 洛谷 P3372 【模板】线段树 1）。

2025/8/13

更新了快读快写。

2025/8/9

更新了手写的高精度加减法、高精度乘法。

FastOI 模板

#include<bits/stdc++.h>
#define ll long long
//#define getchar getchar_unlocked
namespace fastIO{
#define ll long long
	void readInt(int& n){
		n=0;bool neg=false;char c=getchar();
		while(!isdigit(c))neg|=(c=='-'),c=getchar();
		while(isdigit(c))n=(n<<1)+(n<<3)+c-48,c=getchar();
		if(neg)n=-n;
	}
	void readLL(ll& n){
		n=0;bool neg=false;char c=getchar();
		while(!isdigit(c))neg|=(c=='-'),c=getchar();
		while(isdigit(c))n=(n<<1)+(n<<3)+c-48,c=getchar();
		if(neg)n=-n;
	}
	void writeInt(int n){
		if(n==0){putchar('0');return;}
		if(n<0){putchar('-'),n=-n;}
		int s[25];int*p=s;
		while(n!=0)*(++p)=n%10,n/=10;
		while(p!=s)putchar(*(p--)+48);
	}
};
using namespace std;
using namespace fastIO;

int main(){
	
	return 0;
}

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]=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});
	}
	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 upd1(int p,T val){while(p<=SIZE){tree1[p]+=val;p+=lowbit(p);}}
	void upd2(int p,T val){while(p<=SIZE){tree2[p]+=val;p+=lowbit(p);}}
	int qry1(int p){T sum=0;while(p>0){sum+=tree1[p];p-=lowbit(p);}return sum;}
	int qry2(int p){T sum=0;while(p>0){sum+=tree2[p];p-=lowbit(p);}return sum;}
public:
	void updata(int l,int r,T val){
		upd1(l,val);upd1(r+1,-val);
		upd2(l,(l-1)*val);upd2(r+1,-(r*val));
	}
	T range(int l,int r){
		return qry1(r)*r-qry2(r)-qry1(l-1)*(l-1)+qry2(l-1);
	}
};

线段树（施工ing...）

#include<bits/stdc++.h>
using namespace std;
template<typename T,int SIZE>
class segmentTree{
private:
	T tree[SIZE*4],tag[SIZE*4];
	int n=0;
	T calc(const T& x,const T& y){
		return x+y;
		//TODO
	}
	void tag_add(int lb,int ub,int p,const T val){
		tree[p]+=(ub-lb+1)*val;
		tag[p]+=val;
	}
	void tag_pushdown(const int&lb,const int&ub,const int&p){
		if(!tag[p])return;
		int mid=(lb+ub)>>1;
		tag_add(lb,mid,p<<1,tag[p]);
		tag_add(mid+1,ub,p<<1|1,tag[p]);
		tag[p]=0;
	}
	void _built(const int lb,const int ub,const int p,const T* it){
		if(lb==ub){tree[p]=*(it+p);return;}
		int mid=(lb+ub)>>1;
		_built(lb,mid,p<<1,it);
		_built(mid+1,ub,p<<1|1,it);
		tree[p]=tree[p<<1]+tree[p<<1|1];
	}
	T _query(int lb,int ub,int p,const int l,const int r){
		if(l<=lb&&ub<=r)return tree[p];
		T sum=0;
		int mid=(lb+ub)>>1;
		tag_pushdown(lb,ub,p);
		if(l<=mid)sum=calc(_query(lb,mid,p<<1,l,r),sum);
		if(r>mid)sum=calc(_query(mid+1,ub,p<<1|1,l,r),sum);
		return sum;
	}
	void _update(int lb,int ub,int p,const T val,const int l,const int r){
		if(l<=lb&&ub<=r){
			tag_add(lb,ub,p,val);
			return;
		}
		int mid=(lb+ub)>>1;
		tag_pushdown(lb,ub,p);
		if(l<=mid)_update(lb,mid,p<<1,val,l,r);
		if(mid<r)_update(mid+1,ub,p<<1|1,val,l,r);
		tree[p]=tree[p<<1]+tree[p<<1|1];
	}
public:
	void built(const int&l,const int&r,const T*it){
		_built(l,r,1,it);
		n=max(n,r);
	}
	void update(const int&l,const int&r,const T&val){
		_update(1,n,1,val,l,r);
	}
	T query(const int&l,const int&r){
		return _query(1,n,1,l,r);
	}
};
constexpr int N=1e5+5;
int n,q;
long long a[N];
segmentTree<long long,N> smt;
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%lld",a+i);
	smt.built(1,n,a);
	while(q--){
		int opt,x,y;
		long long val;
		scanf("%d%d%d",&opt,&x,&y);
		if(opt==1){
			scanf("%lld",&val);
			smt.update(x,y,val);
		}else{
			long long ans=smt.query(x,y);
			printf("%lld\n",ans);
		}
	}
	return 0;
}

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

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;}//小根堆

高精度计算

手写

这个 78 玩意浪费了我三天时间……

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int N=20050;
struct Bignum{
	int len=0,a[N];
	
	int& operator[](size_t p){return a[p];}
	const int& operator[](size_t p)const{return a[p];}
	bool isdight(char ch){return '0'<=ch&&ch<='9';}
	void reverse(){for(int i=1;i<=len/2;i++)swap(a[i],a[len-i+1]);}
	void fread(){
		len=0;
		char ch=getchar();
		while(ch=='0')ch=getchar();
		while(isdight(ch))a[++len]=ch-'0',ch=getchar();
		reverse();
	}
	void read(){
		len=0;
		string str;
		cin>>str;
		for(int i=str.size()-1;i>=0;i--)a[++len]=str[i]-'0';
		while(a[len]==0)len--;
	}
	void print(){if(len==0)putchar('0');for(int i=len;i>0;i--)putchar(a[i]+'0');}
	void println(){print();putchar('\n');}
	
	void clear(){for(int i=1;i<=len;i++)a[i]=0;len=0;}
	
	void copynum(ll x){
		len=0;
		while(x>0)a[++len]=x%10,x/=10;
	}
	void copy(Bignum x){
		for(int i=1;i<=x.len;i++)a[i]=x[i];
		len=x.len;
	}
	
	bool operator==(const Bignum& b)const{
		if(len!=b.len)return false;
		for(int i=len;i>=0;i--){
			if(a[i]!=b[i])return false;
		}
		return true;
	}
	bool operator==(const ll& b)const{
		Bignum c;c.copynum(b);
		return *this==c;
	}
	bool operator!=(const Bignum& b)const{
		return !(*this==b);
	}
	bool operator!=(const ll& b)const{
		return !(*this==b);
	}
	bool operator<(const Bignum& b)const{
		if(len<b.len)return true;
		if(len>b.len)return false;
		for(int i=len;i>=1;i--){
			if(a[i]<b[i])return true;
			if(a[i]>b[i])return false;
		}
		return false;
	}
	bool operator<(const ll& b)const{
		Bignum c;c.copynum(b);
		return *this<c;
	}
	bool operator>(const Bignum& b)const{
		if(len>b.len)return true;
		if(len<b.len)return false;
		for(int i=len;i>=1;i--){
			if(a[i]>b[i])return true;
			if(a[i]<b[i])return false;
		}
		return false;
	}
	bool operator>(const ll& b)const{
		Bignum c;c.copynum(b);
		return *this>c;
	}
	bool operator<=(const Bignum& b)const{return !(*this>b);}
	bool operator<=(const ll& b)const{return !(*this>b);}
	bool operator>=(const Bignum& b)const{return !(*this<b);}
	bool operator>=(const ll& b)const{return !(*this<b);}
	
	Bignum operator+(const Bignum& b)const{
		Bignum c;
		int add=0;
		for(int i=1;i<=max(len,b.len);i++){
			c[i]=(a[i]+b[i]+add)%10;
			if(add+a[i]+b[i]>9)add=1;
			else add=0;
		}
		c.len=max(len,b.len);
		if(add==1)c[++c.len]=1;
		return c;
	}
	void operator+=(const Bignum& b){*this=*this+b;}
	Bignum operator-(const Bignum& b)const{
		Bignum c;
		for(int i=1;i<=max(len,b.len)+1;i++)c[i]=0;
		for(int i=1;i<=max(len,b.len)+1;i++){
			c[i]+=a[i]-b[i];
			if(c[i]<0)c[i+1]--,c[i]+=10;
		}
		c.len=max(len,b.len);
		while(!c[c.len]&&c.len>1)c.len--;
		return c;
	}
	void operator-=(const Bignum& b){*this=*this-b;}
	Bignum operator*(const Bignum& b)const{
		if(*this==0)return *this;
		if(b==0)return b;
		Bignum c,t;
		for(int i=1;i<=len+b.len;i++)c[i]=0;
		for(int i=1;i<=len;i++){
			int add=0;
			t[i-1]=0;
			for(int j=1;j<=b.len;j++){
				int k=a[i]*b[j]+add;
				t[i+j-1]=k%10;
				add=k/10;
			}
			t.len=i+b.len-1;
			if(add>0)t[++t.len]=add;
			c=c+t;
		}
		return c;
	}
	void operator*=(const Bignum& b){*this=(*this)*b;}
};
void write(Bignum x){if(x.len==0)putchar('0');for(int i=x.len;i>=1;i--)putchar(x[i]+'0');}
void writeln(Bignum x){write(x);putchar('\n');}
Bignum n,m,k;
int main(){
	n.read();
	m.read();
	if(n<m)swap(n,m);
	write(n-m);
	return 0;
}
/*
69 473
= 32637
*/

高精度

#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;
		}
	}
}

神犇的 Blog