矩阵快速幂
参考题目：https://codeforces.com/problemset/problem/678/D
#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define int long long
#define ll long long
#define MOD 1000000007
using namespace std;
const int MAXN = 10;
struct Matrix
{
ll mat[MAXN][MAXN];
};
Matrix P;
Matrix I; //单位矩阵
Matrix Mul_Matrix(Matrix a, Matrix b , ll mod)
{
Matrix c;
for(int i = 0 ; i < MAXN ; i ++)
for(int j = 0 ; j < MAXN ; j ++)
{
c.mat[i][j] = 0;
for(int k = 0 ; k < MAXN ; k ++)
{
c.mat[i][j] += (a.mat[i][k] * b.mat[k][j]) % mod;
c.mat[i][j] %= mod;
}
}
return c;
}
Matrix pow_mod_Matrix(Matrix P , ll n , ll mod)
{
Matrix ans = I, b = P;
while(n)
{
if(n & 1) ans = Mul_Matrix(ans , b , mod);
n >>= 1;
b = Mul_Matrix(b , b , mod);
}
return ans;
}
void Matrix_init()
{
for(int i = 0 ; i < MAXN ; i ++) I.mat[i][i] = 1;
}
signed main()
{
ios;
int a , b , n , x;
cin >> a >> b >> n >> x;
Matrix_init();
{
P.mat[0][0] = a, P.mat[0][1] = 0;
P.mat[1][0] = 1, P.mat[1][1] = 1;
Matrix res = pow_mod_Matrix(P , n , MOD);
ll ans = x * res.mat[0][0] + b * res.mat[1][0];
ans = (ans % MOD + MOD) % MOD;
cout << ans << '
';
}
return 0;
}
Dijkstra堆优化
参考题目：https://www.luogu.com.cn/problem/P4779
#include<bits/stdc++.h>
#define int long long
#define rep(i , a , b) for(int i = a ; i <= b ; i ++)
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
struct node{
int dis , pos;
bool operator <( const node &x )const{
return x.dis < dis;
}
};
struct Edge{
int to , dis , nex;
}edge[N << 1];
int head[N], dis[N] , tot , vis[N] , n , m , s;
inline void add_edge(int u , int v , int d)
{
edge[++ tot].dis = d;
edge[tot].to = v;
edge[tot].nex = head[u];
head[u] = tot;
}
inline void dijkstra(int s)
{
memset(dis , inf , sizeof(dis)) ;
dis[s] = 0;
priority_queue <node> que;
que.push(node{0, s});
while(!que.empty())
{
node tmp = que.top();
que.pop();
int u = tmp.pos, d = tmp.dis;
if(vis[u]) continue;
vis[u] = 1;
for(int i = head[u] ; i ; i = edge[i].nex)
{
int v = edge[i].to;
if(dis[v] > dis[u] + edge[i].dis)
{
dis[v] = dis[u] + edge[i].dis;
if(!vis[v]) que.push(node{dis[v] , v});
}
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin >> n >> m >> s;
rep(i , 1 , m)
{
int u , v , w;
cin >> u >> v >> w;
add_edge(u , v , w);
}
dijkstra(s);
rep(i , 1 , n) cout << dis[i] << " ";
cout << '
';
return 0;
}
Dijkstra配对堆
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define il inline
using namespace std;
using namespace __gnu_pbds;
const int inf (0x3f3f3f3f);
typedef __gnu_pbds::priority_queue< pair<int,int> ,greater< pair<int,int> >,pairing_heap_tag > heap;
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');}
const int N = 2e5 + 10;
heap que;
heap::point_iterator id[N];
struct Edge{
int nex , to , w;
}edge[N << 1];
int head[N] , tot;
il void add_edge(int u , int v , int w)
{
edge[++ tot].nex = head[u];
edge[tot].to = v;
edge[tot].w = w;
head[u] = tot;
}
int n , m , s , dis[N];
il void dij(int st)
{
memset(dis , inf , sizeof(dis));
dis[st] = 0;
id[st] = que.push(make_pair(0 , st));
while(!que.empty())
{
int u = que.top().second;
que.pop();
for(int i = head[u] ; i ; i = edge[i].nex)
{
int v = edge[i].to ;
int w = edge[i].w ;
if(w + dis[u] < dis[v])
{
dis[v] = dis[u] + edge[i].w;
if(id[edge[i].to] != 0) que.modify(id[v] , make_pair(dis[v] , v));
else id[v] = que.push(make_pair(dis[v] , v));
}
}
}
}
signed main()
{
read(n) , read(m) , read(s);
rep(i , 1 , m)
{
int u , v , w;
read(u) , read(v) , read(w);
add_edge(u , v , w);
}
dij(s);
rep(i , 1 , n) Out(dis[i]) , putchar(' ');
return 0;
}
Manacher
参考题目：https://www.luogu.com.cn/problem/P3805
#include<bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
using namespace std;
const int N = 3e7 + 10;
int pa[N];
string a ;
int Manacher(string a , int *p)
{
string t = "$#";
for(auto i : a) t += i , t += '#';
int mx = 0 , id = 0 ;
int len = t.size() , ans = 0;
for(int i = 1 ; i < len ; i ++)
{
p[i] = mx > i ? min(p[2 * id - i] , mx - i) : 1;
while(t[i + p[i]] == t[i - p[i]]) p[i] ++ ;
if(mx < i + p[i]) mx = i + p[i] , id = i;
ans = max(ans , p[i] - 1);
}
return ans;
}
signed main()
{
ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
cin >> a ;
cout << Manacher(a , pa) << '
';
return 0;
}
主席树
参考题目：https://www.luogu.com.cn/problem/P3834
#include<bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<=n;i++)
using namespace std;
const int N = 3e5 + 10;
struct Chairman_Tree{
int l , r , sum;
}Ctree[N << 5];
vector<int>vec;
int root[N] , a[N] , Ctot;
void update(int l , int r , int pre , int &now , int pos)
{
Ctree[++ Ctot] = Ctree[pre];
Ctree[Ctot].sum ++ ;
now = Ctot;
if(l == r) return ;
int mid = l + r >> 1;
if(pos <= mid) update(l , mid , Ctree[pre].l , Ctree[now].l , pos);
else update(mid + 1 , r , Ctree[pre].r , Ctree[now].r , pos);
}
int query(int l , int r , int L , int R , int k)
{
if(l == r) return l ;
int mid = l + r >> 1;
int cha = Ctree[Ctree[R].l].sum - Ctree[Ctree[L].l].sum;
if(cha >= k) return query(l , mid , Ctree[L].l , Ctree[R].l , k);
else return query(mid + 1 , r , Ctree[L].r , Ctree[R].r , k - cha);
}
int get_id(int x)
{
return lower_bound(vec.begin() , vec.end() , x) - vec.begin() + 1;
}
signed main()
{
ios::sync_with_stdio(false);
int n , m ;
cin >> n >> m;
rep(i , 1 , n)
{
cin >> a[i];
vec.push_back(a[i]);
}
sort(vec.begin() , vec.end());
vec.erase(unique(vec.begin() , vec.end()) , vec.end()) ;
rep(i , 1 , n)
update(1 , n , root[i - 1] , root[i] , get_id(a[i]));
while(m --)
{
int l , r , k;
cin >> l >> r >> k ;
int pos = query(1 , n , root[l - 1] , root[r] , k);
cout << vec[pos - 1] << '
' ;
}
return 0;
}
二次剩余
*参考题目：https://www.luogu.com.cn/problem/P5491*
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll w;
struct num
{
ll x, y;
};
num mul(num a, num b, ll p)
{
num ans = {0, 0};
ans.x = ((a.x * b.x % p + a.y * b.y % p * w % p) % p + p) % p;
ans.y = ((a.x * b.y % p + a.y * b.x % p) % p + p) % p;
return ans;
}
ll powwR(ll a, ll b, ll p)
{
ll ans = 1;
while (b)
{
if (b & 1)
ans = 1ll * ans % p * a % p;
a = a % p * a % p;
b >>= 1;
}
return ans % p;
}
ll powwi(num a, ll b, ll p)
{
num ans = {1, 0};
while (b)
{
if (b & 1)
ans = mul(ans, a, p);
a = mul(a, a, p);
b >>= 1;
}
return ans.x % p;
}
ll M_sqrt(ll n, ll p)
{
n %= p;
if (p == 2)
return n;
if (powwR(n, (p - 1) / 2, p) == p - 1)
return -1; //不存在
ll a;
while (1)
{
a = rand() % p;
w = ((a * a % p - n) % p + p) % p;
if (powwR(w, (p - 1) / 2, p) == p - 1)
break;
}
num x = {a, 1};
return powwi(x, (p + 1) / 2, p);
}
signed main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t --)
{
ll n , p;
cin >> n >> p ;
if(!n)
{
cout << 0 << '
' ;
continue ;
}
ll ans1 = M_sqrt(n , p) , ans2;
if(ans1 == -1) cout << "Hola!
";
else
{
ans2 = p - ans1;
if(ans1 > ans2) swap(ans1 , ans2);
if(ans1 == ans2) cout << ans1 << '
';
else cout << ans1 << " " << ans2 << '
' ;
}
}
return 0;
}
KMP
参考题目：https://www.luogu.com.cn/problem/P3375
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int nex[N] ;
vector<int>ans;
string s , t;
void get_nex(string s , int *nex)
{
int i = 0 , j = -1 , len = s.size();
nex[i] = j;
while(i < len)
{
while(j != -1 && s[i] != s[j]) j = nex[j];
nex[++ i] = ++ j ;
}
}
void KMP(string s , string t)
{
get_nex(t , nex) ;
int i = 0 , j = 0 , lens = s.size() , lent = t.size();
while(i < lens)
{
while(j != -1 && s[i] != t[j]) j = nex[j];
i ++ , j ++ ;
if(j == lent) ans.push_back(i - lent + 1);
}
}
signed main()
{
ios::sync_with_stdio(false);
cin >> s >> t ;
KMP(s , t);
for(auto i : ans) cout << i << '
' ;
for(int i = 1 ; i <= t.size() ; i ++ ) cout << nex[i] << " ";
cout << '
';
return 0;
}
MatrixTree矩阵树——求无向图生成树个数
参考题目：https://www.luogu.com.cn/problem/SP104
#include<bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define int long long
#define ll long long
using namespace std;
const int N = 2e2 + 10;
const double eps = 1e-12;
int G[N][N];
int n , m;
int dcmp(int x)
{
if(x <= eps || x >= -eps) return 0;
else return x < 0 ? -1 : 1;
}
void init(int n)
{
rep(i , 0 , n) rep(j , 0 , n) G[i][j] = 0;
}
ll Gauss(int n)
{
ll ans = 1;
rep(i , 1 , n - 1)
{
rep(k , i + 1 , n - 1)
{
while(G[k][i])
{
int d = G[i][i] / G[k][i];
rep(j , i , n - 1) G[i][j] = (G[i][j] - 1LL * d * G[k][j]);
swap(G[i] , G[k]) , ans = -ans;
}
}
ans = 1LL * ans * G[i][i];
}
return ans;
}
signed main()
{
ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
int T = 1;
cin >> T;
while(T --)
{
cin >> n >> m;
init(n);
rep(i , 1 , m)
{
int x , y ;
cin >> x >> y ;
G[x][x] ++ , G[y][y] ++;
G[x][y] -- , G[y][x] --;
}
int tot = Gauss(n);
cout << tot << '
';
}
return 0;
}
AC自动机—fail树
参考题目：https://www.luogu.com.cn/problem/P5357
#include<bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define int long long
#define ll long long
using namespace std;
const int N = 3e5 + 10;
struct Edge{
int nex , to;
}edge[N << 1];
int head[N] , TOT;
void add_edge(int u , int v)
{
edge[++ TOT].nex = head[u] ;
edge[TOT].to = v;
head[u] = TOT;
}
int cnt[N] , fail[N] , num[N];
int tree[N][26];
int tot = 0;
void del(int x)
{
cnt[x] = 0 , fail[x] = 0;
rep(i , 0 , 25) tree[x][i] = 0;
}
void insert(string s , int id)
{
int root = 0;
for(auto i : s)
{
int x = i - 'a';
if(!tree[root][x])
{
tree[root][x] = ++ tot;
del(tot);
}
root = tree[root][x];
}
num[id] = root;
}
void build()
{
queue<int>que;
rep(i , 0 , 25) if(tree[0][i])
{
int v = tree[0][i];
fail[v] = 0;
que.push(v);
}
while(!que.empty())
{
int u = que.front();
que.pop();
rep(i , 0 , 25)
{
if(tree[u][i])
{
int v = tree[u][i];
fail[v] = tree[fail[u]][i];
que.push(v);
}
else tree[u][i] = tree[fail[u]][i];
}
}
}
void query(string s)
{
int p = 0 , res = 0;
for(auto i : s)
{
int x = i - 'a';
p = tree[p][x] ;
cnt[p] ++ ;
}
}
string st[N] , s;
void dfs(int u , int far)
{
for(int i = head[u] ; i ; i = edge[i].nex)
{
int v = edge[i].to ;
if(v == far) continue ;
dfs(v , u);
cnt[u] += cnt[v];
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int n , T = 1;
cin >> n;
rep(i , 1 , n) cin >> st[i] , insert(st[i] , i);
build();
cin >> s;
query(s);
rep(i , 1 , tot) add_edge(fail[i] , i);
dfs(0 , -1);
rep(i , 1 , n) cout << cnt[num[i]] << '
';
return 0;
}
参考题目：https://www.luogu.com.cn/problem/P3796
#include<bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
using namespace std;
const int N = 1e6 + 10;
int cnt[N] , fail[N] , num[N];
int tree[N][26];
int tot = 0;
struct Edge{
int nex , to;
}edge[N << 1];
int head[N] , TOT;
void add_edge(int u , int v)
{
edge[++ TOT].nex = head[u] ;
edge[TOT].to = v;
head[u] = TOT;
}
void del(int x)
{
cnt[x] = 0 , fail[x] = 0;
rep(i , 0 , 25) tree[x][i] = 0;
}
void insert(string s , int id)
{
int root = 0;
for(auto i : s)
{
int x = i - 'a';
if(!tree[root][x])
{
tree[root][x] = ++ tot;
del(tot);
}
root = tree[root][x];
}
num[id] = root;
}
void build()
{
queue<int>que;
rep(i , 0 , 25) if(tree[0][i])
{
int v = tree[0][i];
fail[v] = 0;
que.push(v);
}
while(!que.empty())
{
int u = que.front();
que.pop();
rep(i , 0 , 25)
{
if(tree[u][i])
{
int v = tree[u][i];
fail[v] = tree[fail[u]][i];
que.push(v);
}
else tree[u][i] = tree[fail[u]][i];
}
}
}
int query(string s)
{
int p = 0 , res = 0;
for(auto i : s)
{
int x = i - 'a';
p = tree[p][x] ;
int fi = p;
cnt[fi] ++ ;
}
return res;
}
void dfs(int u , int far)
{
for(int i = head[u] ; i ; i = edge[i].nex)
{
int v = edge[i].to;
if(v == far) continue ;
dfs(v , u);
cnt[u] += cnt[v];
}
}
string st[N] , s;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int n , T = 1;
while(cin >> n && n)
{
rep(i , 1 , n) cin >> st[i] , insert(st[i] , i);
build();
cin >> s;
query(s);
rep(i , 1 , tot) add_edge(fail[i] , i);
dfs(0 , -1);
int ans = 0;
rep(i , 1 , n) ans = max(ans , cnt[num[i]]);
cout << ans << '
';
rep(i , 1 , n) if(ans == cnt[num[i]]) {cout << st[i] << '
';}
del(0);
tot = 0;
memset(head , 0 , sizeof(head)) , TOT = 0;
}
return 0;
}
AC自动机—fail指针乱跳版
参考题目：https://www.luogu.com.cn/problem/P3808
#include<bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
using namespace std;
const int N = 1e6 + 10;
int cnt[N] , fail[N];
int tree[N][26];
int tot = 0;
string s;
void del(int x)
{
cnt[x] = 0 , fail[x] = 0;
rep(i , 0 , 25) tree[x][i] = 0;
}
void insert(string s)
{
int root = 0;
for(auto i : s)
{
int x = i - 'a';
if(!tree[root][x])
{
tree[root][x] = ++ tot;
del(tot);
}
root = tree[root][x];
}
cnt[root] ++ ;
}
void build()
{
queue<int>que;
rep(i , 0 , 25) if(tree[0][i])
{
int v = tree[0][i];
fail[v] = 0;
que.push(v);
}
while(!que.empty())
{
int u = que.front();
que.pop();
rep(i , 0 , 25)
{
if(tree[u][i])
{
int v = tree[u][i];
fail[v] = tree[fail[u]][i];
que.push(v);
}
else tree[u][i] = tree[fail[u]][i];
}
}
}
int query(string s)
{
int p = 0 , res = 0;
for(auto i : s)
{
int x = i - 'a';
p = tree[p][x] ;
int fi = p;
while(fi && cnt[fi] != -1)
{
res += cnt[fi];
cnt[fi] = -1;
fi = fail[fi];
}
}
return res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int n , T = 1;
while(T --)
{
cin >> n;
rep(i , 1 , n) cin >> s , insert(s);
build();
cin >> s;
cout << query(s) << '
';
del(0);
tot = 0;
}
return 0;
}
网络流—预流推进HLPP
参考题目：https://www.luogu.com.cn/problem/P4722
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = INT_MAX;
const ll INF = (0x3f3f3f3f3f3f3f3fll);
const int maxn = 1.2e3 + 5;
struct HLPP
{
struct Edge
{
int v, rev;
ll cap;
};
int n, sp, tp, lim, ht, lcnt;
ll exf[maxn];
vector<Edge> G[maxn];
vector<int> hq[maxn], gap[maxn], h, sum;
void init(int nn, int s, int t)
{
sp = s, tp = t, n = nn, lim = n + 1, ht = lcnt = 0;
for(int i = 1; i <= n; ++i) G[i].clear(), exf[i] = 0;
}
void add_edge(int u, int v, ll cap)
{
G[u].push_back( {v, (int)(G[v].size()) , cap});
G[v].push_back( {u, (int)(G[u].size()) - 1, 0});
}
void update(int u, int nh)
{
++lcnt;
if(h[u] != lim) --sum[h[u]];
h[u] = nh;
if(nh == lim) return;
++sum[ht = nh];
gap[nh].push_back(u);
if(exf[u] > 0) hq[nh].push_back(u);
}
void relabel()
{
queue<int> q;
for(int i = 0; i <= lim; ++i) hq[i].clear(), gap[i].clear();
h.assign(lim, lim), sum.assign(lim, 0), q.push(tp);
lcnt = ht = h[tp] = 0;
while(!q.empty())
{
int u = q.front();
q.pop();
for(Edge &e : G[u]) if(h[e.v] == lim && G[e.v][e.rev].cap) update(e.v, h[u] + 1), q.push(e.v);
ht = h[u];
}
}
void push(int u, Edge &e)
{
if(!exf[e.v]) hq[h[e.v]].push_back(e.v);
ll df = min(exf[u], e.cap);
e.cap -= df, G[e.v][e.rev].cap += df;
exf[u] -= df, exf[e.v] += df;
}
void discharge(int u)
{
int nh = lim;
if(h[u] == lim) return;
for(Edge &e : G[u])
{
if(!e.cap) continue;
if(h[u] == h[e.v] + 1)
{
push(u, e);
if(exf[u] <= 0) return;
}
else if(nh > h[e.v] + 1) nh = h[e.v] + 1;
}
if(sum[h[u]] > 1) update(u, nh);
else
{
for( ; ht >= h[u]; gap[ht--].clear())
for(int &i : gap[ht]) update(i, lim);
}
}
ll hlpp()
{
exf[sp] = INF, exf[tp] = -INF, relabel();
for(Edge &e : G[sp]) push(sp, e);
for( ; ~ht; --ht)
{
while(!hq[ht].empty())
{
int u = hq[ht].back();
hq[ht].pop_back();
discharge(u);
if(lcnt > (n << 2)) relabel();
}
}
return exf[tp] + INF;
}
}hp;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int n, m, s, t, u, v, w;
cin >> n >> m >> s >> t;
hp.init(n, s, t);
while(m --)
{
cin >> u >> v >> w;
hp.add_edge(u, v, w);
}
cout << hp.hlpp() << '
';
return 0;
}
网络流—dinic
参考题目：https://www.luogu.com.cn/problem/P3376
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define int long long
#define ll long long
using namespace std;
const ll INF (0x3f3f3f3f3f3f3f3fll);
const int inf = 0x3f3f3f3f3f;
const int N = 3e5 + 10;
struct Edge{
int nex , to;
}edge[N << 1];
int head[N] , TOT;
void add_edge(int u , int v)
{
edge[++ TOT].nex = head[u] ;
edge[TOT].to = v;
head[u] = TOT;
}
const int Max = 1e5 + 10;
struct Dinic
{
struct Edge
{
int to, nex, flow; //flow记录这条边当前的边残量
} edge[Max << 1];
int n, m, s, t;
int head[Max], TOT;
int dis[Max] , cur[Max];
void init(int nn , int ss , int tt)
{
this->n = nn , this->s = ss , this->t = tt;
TOT = 1;
for(int i = 0 ; i <= nn + 1 ; i ++) head[i] = 0;
}
void add_edge(int u , int v , int flow)
{
edge[++ TOT].nex = head[u];
edge[TOT].to = v;
edge[TOT].flow = flow;
head[u] = TOT;
edge[++ TOT].nex = head[v];
edge[TOT].to = u;
edge[TOT].flow = 0;
head[v] = TOT;
}
bool bfs() //判断图是否连通
{
queue<int>que;
memset(dis, -1, (max(n + 5 , t + 5)) * sizeof(int));
dis[s] = 0;
que.push(s);
while(!que.empty())
{
int u = que.front();
que.pop();
for(int i = head[u]; i; i = edge[i].nex)
{
int v = edge[i].to;
if(dis[v] == -1 && edge[i].flow > 0) //可以借助边i到达新的结点
{
dis[v] = dis[u] + 1; //求顶点到源点的距离编号
que.push(v);
}
}
}
return dis[t] != -1; //确认是否连通
}
int dfs(int u, int flow_in)
{
if(u == t) return flow_in;
int flow_out = 0; //记录这一点实际流出的流量
for(int i = cur[u]; i; i = edge[i].nex)
{
cur[u] = i; //由于我们增广的时候都是尽量用尽这条边的容量为前提的，
// 那么在在用尽流入流量之前，我们使用的边，都已经满流了
//没有继续增广的可能了，所以抛弃了这些重复的边，从未满流的边开始遍历
int v = edge[i].to;
if(dis[v] == dis[u] + 1 && edge[i].flow > 0)
{
int flow_part = dfs(v, min(flow_in, edge[i].flow));
if(!flow_part)continue; //无法形成增广路
flow_in -= flow_part; //流出了一部分，剩余可分配流入就减少了
flow_out += flow_part; //记录这一点最大的流出
edge[i].flow -= flow_part;
edge[i ^ 1].flow += flow_part; //减少增广路上边的容量，增加其反向边的容量
if(!flow_in) break;
}
}
return flow_out;
}
int dinic()
{
int maxflow = 0;
while(bfs())
{
for(int i = 0; i <= n ; i ++) cur[i] = head[i];
maxflow += dfs(s, inf);
}
return maxflow;
}
}DI;
signed main()
{
ios;
cin.tie(0) , cout.tie(0);
int n , m , s , t;
cin >> n >> m >> s >> t;
DI.init(n , s , t);
rep(i , 1 , m)
{
int u , v , w;
cin >> u >> v >> w;
DI.add_edge(u , v , w);
}
cout << DI.dinic() << '
';
return 0;
}
字符串哈希
参考题目：https://www.luogu.com.cn/problem/P3370
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N = 2e5 + 10;
const int Max = 2e6 + 10;
const ull base = 131;
struct Hash{
ull power[Max] , hash1[Max] , hash2[Max];
ull get_hash1(int l , int r){
return hash1[r] - hash1[l - 1] * power[r - l + 1];
}
ull get_hash2(int l , int r){
return hash2[l] - hash2[r + 1] * power[r - l + 1];
}
void hash_init(int n)
{
power[1] = base;
for(int i = 2 ; i <= n ; i ++) power[i] = power[i - 1] * base;
}
void hash_pre(char *s)
{
int len = strlen(s + 1);
hash1[1] = s[1] - 'a' + 1 , hash1[len + 1] = ' ';
for(int i = 2 ; i <= len ; i ++) hash1[i] = hash1[i - 1] * base + s[i] - 'a' + 1;
}
void hash_suf(char *s)
{
int len = strlen(s + 1);
hash2[len] = s[len] - 'a' + 1 , hash2[len + 1] = ' ';
for(int i = len - 1 ; i >= 1 ; i --) hash2[i] = hash2[i + 1] * base + s[i] - 'a' + 1;
}
}ha;
char s[N];
unordered_map<int , int>mp;
signed main()
{
ha.hash_init(N - 10);
int n , res = 0;
cin >> n;
while(n --)
{
cin >> s + 1;
int len = strlen(s + 1);
ha.hash_pre(s);
int now = ha.get_hash1(1 , len);
if(!mp.count(now)) res ++ , mp[now] ++ ;
}
cout << res << '
';
return 0;
}
可持久化01trie
参考题目：https://www.luogu.com.cn/problem/P4735
#include<bits/stdc++.h>
#define rep(i , a , b) for(int i = a ; i <= b ; i ++)
#define per(i , b , a) for(int i = b ; i >= a ; i --)
using namespace std;
const int N = 1e6 + 10;
int n , m , tot;
int a[N] , sum[N] , cnt[N * 31] , root[N] , tree[N * 31][2];
void insert(int id , int s)
{
root[id] = ++ tot;
int p = root[id] , q = root[id - 1];
per(i , 31 , 0)
{
int x = s >> i & 1;
tree[p][x] = ++ tot;
tree[p][x ^ 1] = tree[q][x ^ 1];
p = tree[p][x] , q = tree[q][x];
cnt[p] = cnt[q] + 1;
}
}
int query(int l , int r , int s)
{
int res = 0 , p = root[r] , q = root[l - 1];
per(i , 31 , 0)
{
int x = s >> i & 1;
if(cnt[tree[p][x ^ 1]] > cnt[tree[q][x ^ 1]])
{
res += 1LL << i;
p = tree[p][x ^ 1] , q = tree[q][x ^ 1];
}
else p = tree[p][x] , q = tree[q][x];
}
return res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
cin >> n >> m ;
rep(i , 1 , n) cin >> a[i] , sum[i] = sum[i - 1] ^ a[i] , insert(i , sum[i]);
while(m --)
{
char op;
cin >> op;
if(op == 'A')
{
cin >> a[++ n];
sum[n] = sum[n - 1] ^ a[n];
insert(n , sum[n]);
}
else
{
int l , r , x;
cin >> l >> r >> x;
if(r == 1)
{
cout << (sum[n] ^ x) << '
';
continue ;
}
cout << query(l - 1 , r - 1 , sum[n] ^ x) << '
';
}
}
return 0;
}
线性求阶层
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10 , mod = 998244353;
int fac[N] , inv[N];
int pow_mod(int x , int n , int mod)
{
int res = 1;
while(n)
{
if(n & 1) res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
void init()
{
int up = N - 10;
fac[0] = 1;
for(int i = 1 ; i <= up ; i ++) fac[i] = fac[i - 1] * i % mod;
inv[up] = pow_mod(fac[up] , mod - 2 , mod);
for(int i = up - 1 ; i >= 0 ; i --) inv[i] = inv[i + 1] * (i + 1) % mod;
}
int C(int n , int m)
{
if(n < m) return 0;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main()
{
init();
int n , m ;
cin >> n >> m ;
cout << C(n , m) << '
';
return 0;
}