目录
- GCD & LCM
- 欧拉函数
- BSGS 算法
- CRT 中国剩余定理
- 原根
有\(a^{x} \equiv b (mod \; p)\),求\(x\)的值。我们可以来推下这个式子,首先,这个\(x \in [0, p]\),我们可以设\(x=im-j\),其中\(m=\lceil \sqrt{p} \rceil\)。显然,\(j \in [0, m], i \in [1, m]\)。式子变成这个样子:
\[a^{im}\equiv a^j b (mod \; p)\]
然后我们只需要求出后半部分,压入 map 中,再枚举前半部分即可求出。
// P3846.cpp #include <bits/stdc++.h> #define ll long long using namespace std; ll p, a, b; ll quick_power(ll base, ll tim) { ll tmp = 1; while (tim) { if (tim & 1) tmp = tmp * base % p; base = base * base % p; tim >>= 1; } return tmp; } map<ll, ll> hashTable; int main() { scanf("%lld%lld%lld", &p, &a, &b); a %= p; if (a == 0) { if (b == 0) printf("0"); else printf("no solution"); return 0; } hashTable.clear(); ll m = ceil(sqrt(p)); for (int j = 0, x = 1; j <= m; j++, x = x * a % p) hashTable[x * b % p] = j; ll unit = quick_power(a, m); for (int i = 1, x = unit; i <= m; i++, x = x * unit % p) if (hashTable.count(x)) { printf("%lld", i * m - hashTable[x]); return 0; } printf("no solution"); return 0; }
一道比较裸的最大流。我们创建源点\(s=0\),让食物从源点连边到每一个牛,牛再创建副本节点(当然主节点和副本节点联通,这样保证只吃一个)连接饮料节点,在连接到汇点。求最大流即可。
// P2891.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 1000, MAX_M = 10000, INF = 0x3f3f3f3f; int head[MAX_N], current, n, f, d, tot, dep[MAX_N], s, t, tmp; struct edge { int to, nxt, weight; } edges[MAX_M << 1]; void addpath(int u, int v, int w) { edges[current].to = v, edges[current].nxt = head[u]; edges[current].weight = w, head[u] = current++; } void add(int u, int v, int w) { addpath(u, v, w), addpath(v, u, 0); } bool bfs() { memset(dep, 0, sizeof(dep)); queue<int> q; q.push(s), dep[s] = 1; do { int u = q.front(); q.pop(); for (int i = head[u]; i != -1; i = edges[i].nxt) if (edges[i].weight > 0 && !dep[edges[i].to]) dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to); } while (!q.empty()); return dep[t] != 0; } int dfs(int u, int flow) { if (u == t || flow == 0) return flow; for (int i = head[u]; i != -1; i = edges[i].nxt) if (dep[edges[i].to] == dep[u] + 1 && edges[i].weight > 0) { int to = edges[i].to; int di = dfs(to, min(flow, edges[i].weight)); if (di > 0) { edges[i].weight -= di, edges[i ^ 1].weight += di; return di; } } return 0; } int dinic() { int ans = 0; while (bfs()) while (int di = dfs(s, INF)) ans += di; return ans; } int main() { memset(head, -1, sizeof(head)); scanf("%d%d%d", &n, &f, &d); s = 0, t = n * 2 + f + d + 1; for (int i = 1; i <= f; i++) add(s, i, 1); for (int i = 1; i <= n; i++) add(i + f, i + f + n, 1); for (int i = 1; i <= d; i++) add(i + 2 * n + f, t, 1); for (int i = 1; i <= n; i++) { int fm, dm; scanf("%d%d", &fm, &dm); while (fm--) scanf("%d", &tmp), add(tmp, i + f, 1); while (dm--) scanf("%d", &tmp), add(f + i + n, tmp + 2 * n + f, 1); } printf("%d", dinic()); return 0; }
一道裸的 2-SAT 模型题,可以作为模板题使用。我们来分析一下:假如第\(i\)对夫妻中的丈夫和第\(j\)对夫妻中的妻子有矛盾,那么说明第\(i\)对夫妻中的丈夫可以和第\(j\)对夫妻中的丈夫坐在一起,或是第\(i\)对夫妻中的妻子可以和第\(j\)对夫妻中的妻子坐在一起。这两种都可以对答案做贡献,所以连边。
连边之后运行 Tarjan,对联通块进行染色。如果对于任意一对夫妻在一个联通块中,那么方案不可行。因为夫妻在一个联通块意味着矛盾总会发生。
// HDU-3062.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 30000; int head[MAX_N], current, n, m, tmp, st[MAX_N], cur, dfn[MAX_N], low[MAX_N], tot; int color[MAX_N], ctot; bool inst[MAX_N]; struct edge { int to, nxt; } edges[4000400]; void addpath(int u, int v) { edges[current].to = v, edges[current].nxt = head[u]; head[u] = current++; } void tarjan(int u) { dfn[u] = low[u] = ++tot, inst[u] = true; st[++cur] = u; for (int i = head[u]; i != -1; i = edges[i].nxt) if (!dfn[edges[i].to]) tarjan(edges[i].to), low[u] = min(low[u], low[edges[i].to]); else if (inst[edges[i].to]) low[u] = min(low[u], dfn[edges[i].to]); if (dfn[u] == low[u]) { ctot++; do { inst[st[cur]] = false, color[st[cur]] = ctot; } while (u != st[cur--]); } } bool solve() { for (int i = 0; i < 2 * n; i++) if (!dfn[i]) tarjan(i); for (int i = 0; i < 2 * n; i += 2) if (color[i] == color[i + 1]) return false; return true; } int main() { while (~scanf("%d%d", &n, &m)) { memset(head, -1, sizeof(head)), memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)), memset(color, 0, sizeof(color)); memset(st, 0, sizeof(st)), memset(inst, 0, sizeof(inst)); for (int i = 1; i <= m; i++) { int a1, a2, c1, c2; scanf("%d%d%d%d", &a1, &a2, &c1, &c2); // reverse the relationship; addpath(2 * a1 + c1, 2 * a2 + 1 - c2); addpath(2 * a2 + c2, 2 * a1 + 1 - c1); } if (solve()) printf("YES\n"); else printf("NO\n"); } return 0; }
类似于之前的 Tarjan 算法,只要\(dfn[u]\leq low[u]\),就可以认为这个点是一个割点。理解:下游的点无法除了通过点 u 的路径到达上游 dfn 更小的点,那么这个就是割点。但是还需要考虑点\(u\)为根节点的情况,因为如果点\(u\)为根的话,那么只要子树大于二就算是一个割点,因为子树间的联通必须需要根节点作为枢纽。
模板题代码:
// P3388.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 20010, MAX_M = 100010; int head[MAX_N], current, n, m, tmpx, tmpy, low[MAX_N], dfn[MAX_N], tot; bool ans[MAX_N]; struct edge { int to, nxt; } edges[MAX_M << 1]; void addpath(int src, int dst) { edges[current].to = dst, edges[current].nxt = head[src]; head[src] = current++; } void tarjan(int u, int fa) { low[u] = dfn[u] = ++tot; int child = 0; for (int i = head[u]; i != -1; i = edges[i].nxt) { if (!dfn[edges[i].to]) { tarjan(edges[i].to, fa), low[u] = min(low[u], low[edges[i].to]); if (low[edges[i].to] >= dfn[u] && u != fa) ans[u] = true; if (u == fa) child++; } low[u] = min(low[u], dfn[edges[i].to]); } if (child >= 2 && u == fa) ans[u] = true; } int main() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); int cnt = 0; for (int i = 1; i <= m; i++) scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy), addpath(tmpy, tmpx); for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, i); for (int i = 1; i <= n; i++) if (ans[i]) cnt++; printf("%d\n", cnt); for (int i = 1; i <= n; i++) if (ans[i]) printf("%d ", i); return 0; }
概念:在无向图中,对于点对\(u,v\),在图上删除除\(u,v\)以外的任意一个点,仍然联通,那么称这个点对为点双联通分量。
概念:在无向图中,对于点对\(u,v\),在图上任意删除一条边,\(u,v\)仍连通,则称其为边双连通分量。
https://www.renfei.org/blog/bipartite-matching.html
二分图中,选取最少的点数,使这些点和所有的边都有关联(把所有的边的覆盖),叫做最小点覆盖。
二分图最小点覆盖 = 二分图最大匹配
二分图最大点独立集 = 总点数 – 二分图最大总匹配
例题:[USACO2006NOV]Asteriod,[Usaco2005 jan]Muddy Fields
模板地址:P3386 【模板】二分图匹配
bool dfs(int u, int tm) { for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (dfn[to] != tm) { dfn[to] = tm; if ((!match[to]) || dfs(match[to], tm)) { match[to] = u; return true; } } } return false; }
我个人认为这个是相当精妙的一个写法,可以将“继续匹配”和“向上协商”完美的结合在一起,非常的优秀。
此模型可以用于求出多个条件约束下变量的解集。可以通过某些矛盾关系推出可行关系做有向边,Tarjan 染色即可。
我们可以使用二分图匹配来做这个题目。我们把每一个小行星的横坐标和纵坐标映射到二分图上,找最大匹配即可。
// POJ3041.cpp #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX_N = 510; int n, k, head[MAX_N], current, tmpx, tmpy, dfn[MAX_N], match[MAX_N], ans; struct edge { int to, nxt; } edges[21000]; void addpath(int src, int dst) { edges[current].to = dst, edges[current].nxt = head[src]; head[src] = current++; } bool dfs(int u, int tm) { for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (dfn[to] != tm) { dfn[to] = tm; if ((!match[to]) || dfs(match[to], tm)) { match[to] = u; return true; } } } return false; } int main() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &k); for (int i = 1; i <= k; i++) scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy); for (int i = 1; i <= n; i++) if (dfs(i, i)) ans++; printf("%d", ans); return 0; }