- 起点
- 宏定义
- __int128
- Stringstream
- O2/O3 优化
- unordered_map的使用以及相关重载
- 数学
- 质数
- 约数
- 欧拉函数
- 逆元
- 组合数
- 欧拉函数
- FFT
- 欧拉筛求积性函数
- 字符串
- KMP
- Trie树
- Manachar算法(求最长回文串长度)
- 字符串哈希
- 图论
- Dijkstra求最短路
- spfa求最短路
- floyd求最短路
- prim算法求最小生成树
- Kruskal 求最小生成树
- 计算几何
起点
宏定义
#include
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0 //仅在linux上可以使用
__int128 read()
{
__int128 x=0,f=1;
char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')f=-1;
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
void print(__int128 x)
{
if(x9)print(x/10);
putchar(x%10+'0');
}
#define eps 1e-8
#define int128 __int128
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a/gcd(a,b)*b
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define debug(x...) do { cout<< #x < "; re_debug(x); } while (0)
void re_debug() { cout< void re_debug(const T& arg,const Ts&... args) { cout< PII;
const int INF=0x3f3f3f3f;
const ll LNF=0x3f3f3f3f3f3f3f3fll;
const double PI=acos(-1.0);
void solve()
{
}
int main()
{
IOS;
int T=1;
cin>>T;
while(T--) solve();
return (0^0);
}
__int128
//这里是因为头文件中#define了,请注意,不要开IOS
int128 read(){
int128 x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch 9)
print(x / 10);
putchar(x % 10 + '0');
}
Stringstream
//1 不要开IOS
//2 记得要cin.get()
string s;
cin.get();
getline(cin,s);
stringstream ssin(s);
string t;
while(ssin>>t)
{
cout<
O2/O3 优化
#pragma GCC optimize(2)
#pragma GCC optimize(3)
unordered_map的使用以及相关重载
struct cmp
{
long long operator()(pair x) const
{
return 1ll*x.first*5221417+x.second;
}
};
unordered_map,int,cmp> umap;
数学
质数
试除法判断质数
bool is_prime(int n)
{
if(n
分解质因数
void divide(int n)
{
for(int i=2;i1) cout<
线性筛
时间复杂度:(O(n))
const int N=1000010;
int primes[N];
bool st[N];
int cnt=0;
void get_primes(int n)
{
for(int i=2;i
约数
试除法求约数
void get_divisors(int n)
{
vector q;
for(int i=1;i
最大公约数
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
欧拉函数
欧拉函数
欧拉函数的定义:
(1 \sim N) 中与 (N) 互质的数的个数被称为欧拉函数，记为 (\phi(N)) 。
若在算数基本定理中， (N=p_{1}^{a_{1}} p_{2}^{a_>{2}} \cdots p_{m}^{a_{m}}) ，则:
(\phi(N)=N \times \frac{p_{1}-1}{p_{1}} \times \frac{p_{2}-1}{p_{2}} \times \ldots \times \frac{p_{m}-1}{p_{m}})
注意: (\phi(1)=1)
int get_phi(int n)
{
int ans=n;
for(int i=2;i1) ans=ans/n*(n-1);
return ans;
}
欧拉筛求欧拉函数
int primes[N];
int phi[N];
bool st[N];
int cnt;
void solve()
{
int n;
scanf("%lld",&n);
phi[1]=1;
for(int i=2;i
逆元
要求 (ax\equiv 1(\bmod m)) (m为质数)$ x\equiv1(\bmod m ) b \text {存在乘法逆元的充要条件是 } b \text { 与模数 } m \text { 互质。当模数 } m \text { 为质数时， } b^{m-2} \text { 即为 } b \text { 的乘法逆元 }$
快速幂求逆元
int qmi(int a,int b,int mod)
{
int ans=1;
while(b)
{
if(b&1) ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
void solve()
{
int a,p;
cin>>a>>p;
if(a%p==0) cout<
扩展欧几里得算法求逆元
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
void solve()
{
int a,p,x,y;
cin>>a>>p;
int d=exgcd(a,p,x,y);
if(d==1) cout<
组合数
求组合数1
适用于数据量小的求法(也可以暴力求)
时间复杂度:(O(n^2))
const int N=1010;
const int mod=1e9+7;
int C[N][N];
void solve()
{
for(int i=0;i
求组合数2 (用逆元求)
时间复杂度:(O( log n))
const int N=100010;
const int mod=1e9+7;
int fact[N];
int infact[N];
int qmi(int a,int b,int mod)
{
int ans=1;
while(b)
{
if(b&1) ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
void init()
{
fact[0]=1;
infact[0]=1;
for(int i=1;i>a>>b;
cout<
卢卡斯定理
适用情况:数字较大,但是模数较小
公式:(C_{a}^{b}(\text { lucas }) \equiv C_{\frac{a}{p}}^{\frac{b}{p}}(\text { lucas }) C_{a \bmod p}^{b \bmod p}(\bmod p))
int qmi(int a,int b,int mod)
{
int ans=1;
while(b)
{
if(b&1) ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
int C(int a,int b,int mod)
{
if(b>a) return 0;
int ans=1;
for(int i=1,j=a;i>a>>b>>mod;
cout<
欧拉函数
(a^{\varphi(n)} \equiv 1(\bmod m))
如果说若(m),(a)为正整数，且(m)和 (a) 互质 那么就成立,当(m)为质数的时候,就是小费马定理
FFT
#include
#include
#include
#include
using namespace std;
const int N = 300010;
const double PI = acos(-1);
int n, m;
struct Complex
{
double x, y;
Complex operator+ (const Complex& t) const
{
return {x + t.x, y + t.y};
}
Complex operator- (const Complex& t) const
{
return {x - t.x, y - t.y};
}
Complex operator* (const Complex& t) const
{
return {x * t.x - y * t.y, x * t.y + y * t.x};
}
}a[N], b[N];
int rev[N], bit, tot;
void fft(Complex a[], int inv)
{
for (int i = 0; i < tot; i ++ )
if (i < rev[i])
swap(a[i], a[rev[i]]);
for (int mid = 1; mid < tot; mid <> 1] >> 1) | ((i & 1) << (bit - 1));
fft(a, 1), fft(b, 1);
for (int i = 0; i < tot; i ++ ) a[i] = a[i] * b[i];
fft(a, -1);
for (int i = 0; i
欧拉筛求积性函数
f((a\times b))=f(a)(\times)f(b) 这样的函数叫做积性函数(gcd(a,b)==1)
typedef long long ll;
const int N=1e7+10;
int idx=0;
int cnt[N];//一个数字的最小质因子出现的次数
int primes[N];
bool st[N];
ll f[N];
void solve()
{
int n;
cin>>n;
cout<
字符串
KMP
求next数组
const int N=100010;
char s[N];
int ne[N];
void getnext() //使用数组读入字符串
{
//s是子串
int n;//字符串长度
cin>>n>>s+1;//下标要从1开始读入
for(int i=2;i
KMP匹配
//p是子串,s是模式串
for(int i=1,j=0;i
求最小循环节
//在ne数组上进行求解
for(int i=2;i
Trie树
const int N=2000010*2;
int tr[N][2];//得看对应的情况
int has[N];
int idx=0;
void insert(int x,int add)//add是增量,一般是1/0,表示的是增加和删除
{
int p=0;
for(int i=31;i>=0;i--)
{
int u=(x>>i)&1;
if(!tr[p][u]) tr[p][u]=++idx;
p=tr[p][u];
has[p]+=add;//表示的是有没有这个枝条
}
}
int query(int x)
{
int ans=0;
int p=0;
for(int i=31;i>=0;i--)
{
int u=(x>>i)&1;
if(has[tr[p][!u]])
{
ans+=(1<
Manachar算法(求最长回文串长度)
时间复杂度: (O(n))
p数组不需要memset- 从0开始,字符串
abca会变成$#a$b#c#a#^
const int N=1000010;
char a[N],b[N*2];//a是原来的串,然后b是后来进行扩充的串,
int p[N*2];//包括自身的最长回文串半径
int n;//回文串长度 最终会变成b的回文串长度
void init()
{
int k=0;
b[k++]='$';
b[k++]='#';
for(int i=0;imr)
{
mr=i+p[i];
mid=i;
}
}
}
void solve()
{
cin>>a;//读入字符串
n=strlen(a);
init();
manacher();
}
字符串哈希
- 下标从0开始
struct Hash
{
int size;
static constexpr int base1=20023;
static constexpr int base2=20011;
static constexpr ll mod1=2000000011;
static constexpr ll mod2=3000000019;
vector> hash, pow_base;
Hash(){}
Hash(const string& s)
{
size = s.size();
hash.resize(size);
pow_base.resize(size);
pow_base[0][0] = pow_base[0][1] = 1;
hash[0][0] = hash[0][1] = s[0];
for(int i = 1; i < size; i++){
hash[i][0] = (hash[i - 1][0] * base1 + s[i]) % mod1;
hash[i][1] = (hash[i - 1][1] * base2 + s[i]) % mod2;
pow_base[i][0] = pow_base[i - 1][0]*base1%mod1;
pow_base[i][1] = pow_base[i - 1][1]*base2%mod2;
}
}
array operator[](const array& range)const{
int l=range[0],r=range[1];
if(l==0) return hash[r];
auto single_hash = [&](bool flag){
const ll mod=!flag?mod1:mod2;//注意顺序前面有!
return (hash[r][flag]-hash[l-1][flag]*pow_base[r-l+1][flag]%mod+mod)%mod;
};
return { single_hash(0),single_hash(1)};
}
};
图论
Dijkstra求最短路
#include
using namespace std;
const int N=200010;
typedef pair PII;
int dist[N];
bool st[N];
int e[N],ne[N],w[N],h[N],idx;
void Dijkstra()
{
priority_queue,greater> q;
q.push({0,1});
dist[1]=0;
while(q.size())
{
auto v=q.top().second;
q.pop();
if(st[v]) continue;
st[v]=true;
for(int i=h[v];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[v]+w[i])
{
dist[j]=dist[v]+w[i];
q.push({dist[j],j});
}
}
}
}
spfa求最短路
时间复杂度:(O(nlogn))
const int N=200010;
const int INF=0x3f3f3f3f;
int n,m;
int e[N],ne[N],w[N],h[N],idx;
int dist[N];
bool st[N];
void spfa()
{
memset(dist,INF,sizeof(dist));
queue q;
q.push(1);
dist[1]=0;
st[1]=true;
while(q.size())
{
auto t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
if(!st[j])
{
st[j]=true;
q.push(j);
}
}
}
}
}
floyd求最短路
时间复杂度:(O(n))
const int N=1010;
const int INF=0x3f3f3f3f;
int g[N][N];
int n,m,k;
void init()
{
memset(g,INF,sizeof(g));
for(int i=1;i
prim算法求最小生成树
const int N=510;
bool st[N];
int g[N][N];
int dist[N];
int n,m;
void init()
{
memset(dist,0x3f,sizeof dist);
memset(g,0x3f,sizeof g);
}
void prim()
{
int ans=0;
for(int i=0;idist[j])) t=j;
}
if(i&&dist[t]==0x3f3f3f3f)
{
cout<
Kruskal 求最小生成树
const int N=2e5+10;
int n,m;
int p[N];
struct Node
{
int a,b,w;
bool operator =n-1) cout<
计算几何
#include
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define eps 1e-8
#define int128 __int128
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a/gcd(a,b)*b
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define debug(x...) do { cout<< #x < "; re_debug(x); } while (0)
void re_debug() { cout< void re_debug(const T& arg,const Ts&... args) { cout< PII;
const int INF=0x3f3f3f3f;
const ll LNF=0x3f3f3f3f3f3f3f3fll;
const double PI=acos(-1.0);
int sign(double x)//符号函数
{
if(abs(x)0) return get_lenth(v3);
return distance_to_line(a,b,p);
}
Point get_line_projection(Point a,Point b,Point p)//点p在向量ab的投影的坐标
{
Point v=b-a;
return a+v*(dot(v,p-a)/dot(v,v));
}
bool is_on_segment(Point a,Point b,Point p)//点p是否在线段ab上
{
return sign(cross(p-a,p-b))==0&&sign(dot(p-a,p-b))>T;
while(T--) solve();
return 0^0;
}
Original: https://www.cnblogs.com/Meteor-Z/p/16737164.html
Author: Meteor_Z
Title: ACM-总模板
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604233/
转载文章受原作者版权保护。转载请注明原作者出处！