YIZHIYANG 的动态

记录与收藏都在这里。

粉丝 10

优质贡献者 II优质贡献者 I初来乍到初次互动挑战参与者

动态

P12544 \[UOI 2025\] Boys and Girls

YIZHIYANG初来乍到 2026-9-27 8:21:21

#算法

P12544 [UOI 2025] Boys and Girls思路将问题转化为图论模型。把每个女孩看成一个点，每种男孩看成一条边：

男孩类型

i

对应边

(a_i,b_i)

；

边权为

c_i

。

题目要求选择最大的男孩集合，使得任意两个被选择的男孩至少喜欢同一个女孩。等价于：

在一张带权图中，选择一个最大权边集，使得任意两条边都有公共端点。

关键性质对于一个简单图，如果一个边集合中的任意两条边都有公共端点，那么这个集合只有两种情况。情况 1：所有边经过同一个点例如：1 /|\ / | \ 2 3 4所有边都有公共点

1

。这种情况对应：选择某个女孩，所有喜欢她的男孩都可以加入。设女孩

i

的贡献为：

sum_i=\sum_{e\ni i}w_e

直接统计所有女孩即可。情况 2：三角形例如：1 / \ 2---3三条边：

(1,2),(2,3),(1,3)

任意两条边都有公共点。因此还需要考虑所有三角形的边权和。三角形枚举直接枚举三个点会超时。采用经典的按度数定向。定义：

(deg_u,u)<(deg_v,v)

将边从较小的点指向较大的点。对于一个点

u

，枚举：

u\rightarrow v

然后枚举：

v\rightarrow x

如果存在：

u\rightarrow x

则：

(u,v,x)

构成三角形。复杂度设边数为

m=n

。统计所有星形：

O(n)

枚举三角形：

O(n\sqrt n)

空间复杂度：

O(n)

C++代码#include <bits/stdc++.h> using namespace std; using ll = long long; struct Edge { int a, b; ll c; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int n; cin >> n; int m = 2 * n; vector<Edge> e(n); vector<int> deg(m + 1); vector<ll> sum(m + 1); for (int i = 0; i < n; i++) { int a, b; ll c; cin >> a >> b >> c; e[i] = {a, b, c}; deg[a]++; deg[b]++; sum[a] += c; sum[b] += c; } ll ans = 0; for (int i = 1; i <= m; i++) ans = max(ans, sum[i]); auto cmp = [&](int a, int b) { if (deg[a] != deg[b]) return deg[a] < deg[b]; return a < b; }; vector<vector<pair<int,ll>>> g(m + 1); for (auto [a, b, c] : e) { if (cmp(b, a)) swap(a, b); g[a].push_back({b, c}); } vector<ll> vis(m + 1, -1); for (int u = 1; u <= m; u++) { vector<int> tmp; for (auto [v, w] : g[u]) { vis[v] = w; tmp.push_back(v); } for (auto [v, w1] : g[u]) { for (auto [x, w2] : g[v]) { if (vis[x] != -1) ans = max(ans, w1 + w2 + vis[x]); } } for (int x : tmp) vis[x] = -1; } cout << ans << '\n'; } return 0; }

49 浏览0 点赞0 收藏0 评论

【排序 + 状态压缩背包】掷出重围

YIZHIYANG初来乍到 2026-7-26 11:24:11

#答疑

【排序 + 状态压缩背包】掷出重围关键性质对于已经选定的一组球，投掷顺序不会改变最终被占据的位置集合。考虑交换两个相邻且落点逆序的球，它们的初始落点分别为

a>b

。设从

b

开始的第一个空位置为

u

。

若

u\<a

，从

b

投出的球停在

u

，不会影响从

a

开始寻找空位。

若

u\ge a

，那么区间

\[b,u-1]

已经全部被占据。无论哪个球先投，第一个球都会停在

u

，第二个球都会停在

u

后面的第一个空位。

因此可以不断交换逆序的投掷，相当于按照

w\_i

从小到大投掷。将选择的球按照初始落点排序。假设上一个球最终停在

p

，当前球的初始落点为

w\_i

，那么当前球的最终位置为

\max(w\_i,p+1).

如果

p\<w\_i

，它直接停在

w\_i

。如果

p\ge w\_i

，上一个球的初始落点不超过

w\_i

，而它能够滚动到

p

，说明从

w\_i

到

p

的位置都已被占据，所以当前球停在

p+1

。朴素动态规划可以把已经使用的体力和上一个球的最终位置都放入状态。但

w\_i

最大达到

10^9

，不能直接将实际坐标作为数组下标。关键在于：处理到当前落点

w\_i

时，只需要知道上一个球比

(u,v,x)

多滚出了多少步。这个偏移量最多为选中球的数量，因此不超过

n

。这种把最后落点表示成相对当前

w\_i

的偏移，并在相邻落点之间平移状态的做法，可以将复杂度控制在

O(n^2s)

。(洛谷)状态定义首先把球按照

w\_i

从小到大排序。在处理第

i

个球之前，定义

f\_{j,k}

表示：

已经处理了前

i-1

个球；

总体力消耗恰好为

j

；

当前所有已选球的坐标和最大值；

上一个被投出的球相对于

w\_i

的位置状态为

k

。

其中：

k=0

：没有投出过球，或者上一个球的最终位置小于

w\_i

；

k>0

：上一个球的最终位置为

w\_i+k-1.

只记录最大坐标和，因为状态相同的两个方案中，坐标和较小的方案不会更优。初始状态为

f\_{0,0}=0.

其他状态均为负无穷。投出当前球设当前球消耗体力

x\_i

。如果原状态为

k=0

，当前球停在

w\_i

。如果原状态为

k>0

，上一个球停在

w\_i+k-1

，当前球停在

w\_i+k.

两种情况可以统一写成：当前球最终停在

w\_i+k

，新的偏移状态为

k+1

。因此转移为为了保证每个球最多选择一次，体力

j

必须从大到小枚举。不投出当前球时，状态不需要修改。将基准移动到下一个落点处理完第

i

个球后，状态使用的坐标基准还是

w\_i

。下一个球的基准为

w\_{i+1}

。记

d=w\_{i+1}-w\_i.

若当前

k>0

，最后一个球的位置为

w\_i+k-1.

相对于新的基准

w\_{i+1}

，新的偏移量为

k-d.

如果这个值不大于

0

，说明最后一个球已经位于

w\_{i+1}

左侧，具体位置不再重要，可以统一压缩为状态

0

。因此平移后的状态为

k'=\max(0,k-d).

对于多个状态平移到同一个

k'

的情况，只保留坐标和最大的状态。正确性说明按照前面的交换论证，任意投掷方案都可以调整为按照

w\_i

非递减的顺序投掷，同时最终占据的位置集合不变，因此排序不会遗漏最优方案。处理第

i

个球时，状态

k

准确记录上一个球与当前初始落点的相对关系。

选择当前球时，其最终位置必然为

w\_i+k

，所以选择转移准确模拟了滚动过程。

不选择当前球时，原方案仍然合法。

移动到下一个初始落点后，公式

\max(0,k-d)

准确描述最后位置相对于新基准的偏移。当最后位置位于新基准左侧时，所有这类状态对后续球的影响完全相同，因此可以合并。

每个球只有选择与不选择两种转移，所有体力不超过

s

的子集都会被处理。相同状态只保留最大坐标和不会丢失最优答案，因此最终得到的最大值就是答案。参考实现#include<bits/stdc++.h> using namespace std; using ll = long long; const int N = 505; const ll inf = (1LL << 60); int n, s; pair<ll, int> a[N]; ll f[N][N], g[N]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> s; for (int i = 1; i <= n; i++) { cin >> a[i].first; } for (int i = 1; i <= n; i++) { cin >> a[i].second; } sort(a + 1, a + n + 1); a[n + 1].first = a[n].first; for (int j = 0; j <= s; j++) { for (int k = 0; k <= n; k++) { f[j][k] = -inf; } } f[0][0] = 0; for (int i = 1; i <= n; i++) { ll w = a[i].first; int x = a[i].second; for (int j = s; j >= x; j--) { for (int k = 0; k < i; k++) { if (f[j - x][k] == -inf) { continue; } f[j][k + 1] = max( f[j][k + 1], f[j - x][k] + w + k ); } } ll d = a[i + 1].first - a[i].first; for (int j = 0; j <= s; j++) { for (int k = 0; k <= n; k++) { g[k] = -inf; } for (int k = 0; k <= i; k++) { if (f[j][k] == -inf) { continue; } int t = (int)max(0LL, k - d); g[t] = max(g[t], f[j][k]); } for (int k = 0; k <= n; k++) { f[j][k] = g[k]; } } } ll ans = 0; for (int j = 0; j <= s; j++) { for (int k = 0; k <= n; k++) { ans = max(ans, f[j][k]); } } cout << ans << '\n'; return 0; }复杂度分析排序的时间复杂度为

O(n\log n)

。动态规划中，每个球枚举体力和偏移

84 浏览0 点赞0 收藏0 评论

【独立计数，快速幂】P6075 子集选取

YIZHIYANG初来乍到 2026-7-26 10:47:19

#答疑

【独立计数，快速幂】P6075 子集选取题意概括在一个边长为

k

的三角形中放置若干个集合

A\_{i,j}

。每个集合都必须是

S={1,2,\ldots,n}

的子集，并满足向左和向上包含：$ A\_{i,j}\subseteq A\_{i,j-1}, \qquad A\_{i,j}\subseteq A\_{i-1,j}. $需要统计所有合法的集合放置方案数，答案对

10^9+7

取模。由于

n,k\le 10^9

，不能枚举集合或三角形中的位置，必须推导出答案公式。样例分析当

k=2

时，三个集合之间的关系为

A\_{1,1}\supseteq A\_{2,1}\supseteq A\_{2,2}.

对于任意一个元素，它有四种出现方式：

三个集合中都不出现。

只出现在

A\_{1,1}

。

出现在

A\_{1,1},A\_{2,1}

。

三个集合中都出现。

因此一个元素有

4=2^2

种选择。样例中有两个元素，它们的选择互不影响，所以答案为

w\_i

算法思路不同元素相互独立对于每个元素

x\in S

，只需要确定它是否属于每个

A\_{i,j}

。集合之间的包含关系等价于：如果

x\in A\_{i,j}

，那么在对应位置存在时，必须同时满足

x\in A\_{i,j-1}, \qquad x\in A\_{i-1,j}.

一个元素的出现情况不会影响其他元素。因此，只要算出单个元素有多少种合法出现方式，再将结果取

n

次方即可。每一行都是一个前缀固定一个元素

x

。由于

A\_{i,j}\subseteq A\_{i,j-1},

如果

x

出现在第

i

行的第

j

个集合中，那么它也一定出现在这一行前面的所有集合中。因此，第

k=0

行中包含

x

的位置一定构成一个前缀。设这个前缀的长度为

p\_i

，则

0\le p\_i\le i.

例如

p\_i=3

表示

x \in A\_{i,1},A\_{i,2},A\_{i,3}

，但不属于这一行后面的集合。统计前缀长度序列设

f\_{i,j}

表示处理完前

i

行，并且第

i

行前缀长度为

j

的合法方案数。当

0\le j\<i

时，第

i

行前

j

个位置都包含

x

。根据竖直方向的包含关系，第

i-1

行至少也要包含前

j

个位置。所以前一行的前缀长度

t

必须满足

i

，得到$f_{i,j}\sum_{t=j}^{i-1}f_{i-1,t}. $当

j=i

时，第

i

行全部位置都包含

x

。前

i-1

个位置在上一行都有对应位置，所以第

i-1

行也必须全部包含

x

：

f\_{i,i}=f\_{i-1,i-1}=1.

下面证明$ f\_{i,j}= \begin{cases} 2^{i-j-1},&0\le j\<i,\\ 1,\&j=i. \end{cases} $初始时

i=1

，第一个位置可以不包含或包含

0

，因此

f\_{1,0}=f\_{1,1}=1,

符合公式。假设第

i-1

行的公式成立。对于

j\<i

，有$ \begin{aligned} f\_{i,j} &=\sum\_{t=j}^{i-1}f\_{i-1,t}\\ &=\sum\_{t=j}^{i-2}2^{i-t-2}+1\\ &=2^{i-j-1}. \end{aligned} $因此公式对所有行成立。处理完前

i

行的总方案数为$ \begin{aligned} \sum\_{j=0}^{i}f\_{i,j} &=\sum\_{j=0}^{i-1}2^{i-j-1}+1\\ &=(2^i-1)+1\\ &=2^i. \end{aligned} $所以一个元素在边长为

k

的三角形中共有

2^k

种合法出现方式。计算总答案集合

S

中共有

n

个元素，每个元素都可以独立选择一种合法出现方式。因此总方案数为

(2^k)^n=2^{nk}.

最终只需要使用快速幂计算

2^{nk}\bmod 1000000007.

算法流程

读入

n,k

。

计算指数

nk

。

使用快速幂计算

2^{nk}\bmod 1000000007

。

输出结果。

正确性说明对于任意一个元素

x

，水平方向的包含关系保证它在每一行中的出现位置构成前缀。状态

f\_{i,j}

枚举了第

i

行前缀长度为

j

的所有情况。转移要求上一行的前缀覆盖当前行中具有上方对应位置的所有元素，因此转移得到的方案全部合法。反过来，任意合法出现方式在每一行都有唯一的前缀长度，因此会唯一对应到一条状态转移路径，不会遗漏，也不会重复统计。由状态递推可知，一个元素共有

2^k

种合法出现方式。不同元素的成员关系彼此独立，将每个元素的出现方式组合起来，可以唯一确定所有集合。因此总方案数为

(2^k)^n=2^{nk}.

快速幂计算的正是该值对

10^9+7

取模后的结果，所以算法正确。实现细节与易错点

n

和

k

最大都是

10^9

，因此指数

nk

最大为

10^{18}

，必须使用 long long 保存。不需要利用费马小定理缩小指数。快速幂的循环次数只有

O(\log(nk)),

可以直接处理

10^{18}

级别的指数。参考实现#include<bits/stdc++.h> using namespace std; using ll = long long; const ll md = 1000000007; ll qp(ll a, ll b) { ll r = 1; while(b) { if(b & 1) r = r * a % md; a = a * a % md; b >>= 1; } return r; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, k; cin >> n >> k; cout << qp(2, n * k) << '\n'; return 0; }复杂度分析快速幂需要处理指数

nk

，时间复杂度为

O(\log(nk)).

只使用常数个变量，空间复杂度为

O(1).

71 浏览0 点赞0 收藏0 评论

ABC468F Chmax

YIZHIYANG初来乍到 2026-7-26 10:12:15

#答疑

ABC468F Chmax核心结论是：

删除所有“前缀最大值”，剩余序列记为 $Q$ 。
答案等于“前缀最大值个数”加上 $Q$ 的最长上升子序列长度。

官方题目给出的范围是

N\le 5\times 10^5

，因此需要使用

O(N\log N)

的做法。(AtCoder)关键性质处理完前

i

个数后，一定有

\max(x,y)=\max(P\_1,P\_2,\ldots,P\_i).

因为每个

P\_i

都会被放进

x

或

y

中。1. 遇到新的前缀最大值假设当前数字

P\_i

比之前所有数字都大，那么它也一定大于当前的

x

和

y

。所以无论选择哪一个操作，

c

都必然增加

1

。为了让后续更容易得分，应当把较大的变量更新成

P\_i

，较小的变量保持不变。例如当前

x=8,\quad y=3,\quad P\_i=10,

就令

x=10

，而不是令

y=10

。这样较小值仍然是

3

，后面更容易出现比它大的数。因此，每个前缀最大值都固定贡献

1

。2. 遇到不是前缀最大值的数设当前两个变量分别是

M=\max(x,y),\qquad p=\min(x,y).

因为

P\_i

不是前缀最大值，所以

P\_i\<M.

此时有两种选择：

把

i

放入较大的变量

O(n)

：不会得分，状态也不变。

把

P\_i

放入较小的变量

p

：只有当

P\_i>p

时才能得分，随后

p

变成

P\_i

。

因此，非前缀最大值想要得分，选出的数必须依次严格递增。这正好就是最长上升子序列。举例样例：

P=(4,3,1,2,5).

前缀最大值是

4,5,

固定贡献

2

。删除它们后：

Q=(3,1,2).

Q

的最长上升子序列可以选

1,2,

长度为

2

。所以答案为

2+2=4.

这个结论也是官方题解给出的进一步化简：答案为前缀最大值数量与删除这些元素后序列的 LIS 长度之和。(AtCoder)C++14 代码#include<bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int mx = 0, ans = 0; vector<int> d; for(int i = 1; i <= n; i++) { int x; cin >> x; if(x > mx) { mx = x; ans++; } else { auto it = lower_bound(d.begin(), d.end(), x); if(it == d.end()) d.push_back(x); else *it = x; } } cout << ans + (int)d.size() << '\n'; return 0; }其中 d[i] 表示长度为

i+1

的上升子序列，其末尾元素的最小可能值。使用 lower_bound 维护严格上升子序列。时间复杂度为

O(N\log N),

空间复杂度为

O(N).

80 浏览0 点赞0 收藏0 评论

P6146 [USACO20FEB] Help Yourself G

YIZHIYANG初来乍到 2026-7-26 8:46:55

#答疑

/* 题意：求所有线段子集的并集连通块数量之和。思路：每个连通块由左端点最小的线段唯一代表。扫描端点，当遇到第 k 个左端点时，已有 c 条线段完全结束。让当前线段成为新连通块起点的方案数为 2^(c+n-k)。 */ #include<bits/stdc++.h> using namespace std; using ll=long long; const int mod=1000000007; int l[200005]; int r[200005]; ll pw[100005]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) { int x,y; cin >> x >> y; l[x] = 1; r[y] = 1; } pw[0] = 1; for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * 2 % mod; ll ans = 0; int c = 0; int k = 0; for (int i = 1; i <= 2 * n; i++) { if (l[i]) { k++; ans = (ans + pw[c + n - k]) % mod; } if (r[i]) c++; } cout << ans; return 0; }解题思路直接枚举每个子集显然不行，因为一共有

2^N

个子集。考虑把答案改成计算每条线段的贡献。对于任意一个子集，它的每个连通块中一定存在一条左端点最小的线段，而且这条线段唯一。因此，可以把这个连通块的贡献记在这条线段上。于是问题变成：

对于每条线段，计算有多少个子集使它成为某个连通块中左端点最小的线段。

按照坐标从左到右扫描所有端点。当扫描到某条线段的左端点时，设：

它是第

S={1,2,\ldots,n}

个出现左端点的线段；

已经有

c

条线段的右端点出现，即这些线段已经完全位于当前线段左侧；

还有

k-1-c

条更早开始，但尚未结束的线段。

这

k-1-c

条尚未结束的线段都与当前线段相交。如果选择了其中任意一条，当前线段就会和左端点更小的线段连通，不能成为一个新连通块的起点。因此这些线段必须全部不选。其他线段的选择情况如下：

当前线段必须选择；

已经结束的

c

条线段可以任意选择，共

2^c

种；

尚未开始的

n-k

条线段可以任意选择，共

2^{n-k}

种；

与当前线段相交的早期线段必须全部不选，只有一种选择。

所以当前线段的贡献为

2^c\cdot 2^{n-k}=2^{c+n-k}.

把每个左端点产生的贡献相加即可。例如样例中：

扫描到

1

时，

k=1,c=0

，贡献为

2^{0+3-1}=4

；

扫描到

2

时，

k=2,c=0

，贡献为

2^{0+3-2}=2

；

扫描到

4

时，区间

[2,3]

已结束，

k=3,c=1

，贡献为

2^{1+3-3}=2

。

总答案为

4+2+2=8

。时间复杂度为

O(N)

，空间复杂度为

O(N)

。

90 浏览1 点赞1 收藏0 评论

Miller-Rabin 与 Pollard-Rho

YIZHIYANG初来乍到 2026-7-19 21:21:41

Miller-Rabin 与 Pollard-Rho这两个算法通常配合使用，用来处理较大的整数：

Miller-Rabin：快速判断一个数是不是质数。

Pollard-Rho：快速找到一个合数的非平凡因子。

找到因子后递归分解，就能求出一个大整数的全部质因数。

它们适合处理

10^{18}

范围内的整数。一、为什么普通质因数分解不够判断

n

是否为质数，最直接的方法是枚举

2,3,\ldots,\lfloor\sqrt n\rfloor.

如果

n\le 10^{18}

，那么

\sqrt n\le 10^9.

一次判断可能需要接近

10^9

次运算，无法接受。Miller-Rabin 可以在大约

O(\log n)

次模运算内完成一次检验。Pollard-Rho 则通常能在约

O(n^{1/4})

的期望时间内找到一个因子。二、Miller-Rabin 判素数1. 从费马小定理开始如果

p

是质数，并且

a

不是

p

的倍数，那么

a^{p-1}\equiv 1\pmod p.

因此，若存在一个

a

满足

a^{n-1}\not\equiv 1\pmod n,

那么

M=\max(x,y),\qquad p=\min(x,y).

一定不是质数。但反过来不成立。有些合数对于很多

a

也满足费马小定理，所以仅使用费马检验并不可靠。Miller-Rabin 会进一步检查平方过程中出现的数，从而识别出更多合数。2. 拆分

n-1

对于奇数

n

，将

n-1

写成

n-1=d\cdot 2^s,

其中

d

是奇数。例如

561-1=560=35\cdot 2^4.

所以

d=35,\qquad s=4.

3. 检验过程选择一个底数

a

，先计算

x=a^d\bmod n.

如果

x=1

或者

Q=(3,1,2).

那么这一轮暂时认为

x\_i

可能是质数。否则不断平方：

x\leftarrow x^2\bmod n.

最多平方

s-1

次。如果某次得到

x=n-1,

这一轮检验通过。如果始终没有得到

O(N\log N),

，那么

n

一定是合数。4. 为什么要检查

n-1

对于质数

p

，方程

x^2\equiv 1\pmod p

只有两个解：

x\equiv 1\pmod p

或

x\equiv -1\pmod p.

而模

p

意义下的

-1

就是

p-1

。假设不断平方后最终得到

a^{p-1}\equiv 1\pmod p.

那么在平方链中，第一次变为

1

之前的数必须是

-1

，否则就出现了一个既不是

k'=\max(0,k-d).

也不是

-1

的平方根，与质数的性质矛盾。Miller-Rabin 正是在检查这个过程。5.

64

位整数的固定底数对于无符号

j\<i

位整数，只需要检查下面这些底数，就可以得到确定性结果：$ 2,\ 325,\ 9375,\ 28178,\ 450775,\ 9780504,\ 1795265022. $也就是说，在

64

位整数范围内，这套写法不是概率判素，而是可以当作确定性算法使用。三、Pollard-Rho 找因子Miller-Rabin 只能告诉我们一个数是不是质数。如果

n

是合数，还需要找到它的某个因子。Pollard-Rho 就负责完成这件事。1. 构造伪随机序列选择一个函数

2^k

然后生成序列$ x\_1=f(x\_0),\quad x\_2=f(x\_1),\quad x\_3=f(x\_2),\ldots $由于所有数都在

0

到

n-1

之间，序列最终一定会出现重复，形状类似希腊字母

\rho

，这也是 Pollard-Rho 名字的来源。2. 为什么能找到因子假设

p

是

n

的一个质因子。虽然我们是在模

n

的意义下生成序列，但也可以观察序列模

p

后的结果。因为

p

通常比

n

小，所以序列模

p

后往往会更早发生碰撞。也就是存在两个位置

i,j

，满足

x\_i\equiv x\_j\pmod p.

于是

p\mid x\_i-x\_j.

所以

\gcd(|x\_i-x\_j|,n)

可能得到

p

，或者得到一个包含

p

的非平凡因子。3. Floyd 判环不能保存整个序列，否则空间开销较大。Pollard-Rho 使用快慢指针：

x\leftarrow f(x),

y\leftarrow f(f(y)).

然后计算

d=\gcd(|x-y|,n).

可能出现三种情况：

d=1

暂时没有发现因子，继续移动。

1\<d\<n

找到了一个非平凡因子，可以返回。

d=n

这次随机选择失败，需要重新选择初始值或常数

c

。四、完整分解过程要分解整数

n

，可以递归处理：

如果

n=1

，结束。

使用 Miller-Rabin 判断

n

。

如果

n

是质数，将其加入答案。

否则使用 Pollard-Rho 找到因子

d

。

递归分解

d

和

n/d

。

例如分解

8051\.

Miller-Rabin 判断

8051

是合数。Pollard-Rho 可能找到因子

d=83.

于是

8051=83\times 97.

再分别判断

83

和

97

，二者都是质数，因此最终分解为

8051=83\times 97.

五、C++14 模板#include<bits/stdc++.h> using namespace std; using ll = long long; using i128 = __int128_t; mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); ll mul(ll a, ll b, ll m) { return (i128)a * b % m; } ll qp(ll a, ll b, ll m) { ll r = 1; while (b) { if (b & 1) r = mul(r, a, m); a = mul(a, a, m); b >>= 1; } return r; } bool mr(ll n) { if (n < 2) return 0; for (ll p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) { if (n % p == 0) return n == p; } ll d = n - 1; int s = 0; while ((d & 1) == 0) { d >>= 1; s++; } for (ll a : {2LL, 325LL, 9375LL, 28178LL, 450775LL, 9780504LL, 1795265022LL}) { if (a % n == 0) continue; ll x = qp(a % n, d, n); if (x == 1 || x == n - 1) continue; bool ok = 0; for (int i = 1; i < s; i++) { x = mul(x, x, n); if (x == n - 1) { ok = 1; bre

87 浏览2 点赞0 收藏0 评论

精华

https://www.luogu.com.cn/problem/P14989

YIZHIYANG初来乍到 2026-7-15 21:54:41

#答疑

【最大笛卡尔树，倍增 LCA】传送题意概括有

k

个星球按照编号排成一行。每个星球

A\_{i,j}

有两个传送门：

一个传送到左侧第一个满足

p\_j>p\_i

的星球。

一个传送到右侧第一个满足

p\_j>p\_i

的星球。

如果对应方向不存在更大的星球，这个传送门会传回星球

i

自身。

每次任务会在

n\le 10^{18}

个不同星球上各放置一个机器人。机器人可以任意使用传送门，需要统计有多少个星球能够成为所有机器人的共同到达点。机器人第一次汇合后仍然可以继续一起移动，因此答案统计的不是“第一次汇合的位置”，而是所有机器人都能够到达的星球数量。所有询问中的星球总数为

m

。由于

c

不能对每个机器人单独搜索全部可达点。我们需要找到传送关系中隐藏的树形结构。样例分析样例中的大小序列为

3,1,5,2,7,6,4.

以星球

2

为例，它的大小为

A\_{1,1}

。左边第一个更大的星球是

y

，右边第一个更大的星球是

3

，因此它可以进行如下移动：

2\rightarrow 1\rightarrow 3\rightarrow 5.

所以星球

2

能够到达的星球为

{2,1,3,5}.

星球

4

可以进行如下移动：

4\rightarrow 3\rightarrow 5,

因此它能够到达

{4,3,5}.

二者能够共同到达的星球为

{3,5},

所以任务

2,4

的答案为

2

。这里出现了一个值得注意的现象。机器人每次都会前往一个更大的星球，并且所有可达点似乎排成了一条从当前节点向上的链。这正是最大笛卡尔树中的祖先链。算法思路整体思路左右第一个更大元素之间的关系可以用最大笛卡尔树表示。在这棵树中，每个星球的两个非自环传送门都指向它的祖先，并且其中一个恰好指向父亲。因此，从一个星球出发能够到达的所有星球，正好是它在笛卡尔树上的全部祖先。若一次任务选择了多个星球，那么所有机器人共同能够到达的位置，就是这些星球的公共祖先。所有公共祖先又恰好是它们最近公共祖先的祖先链，因此答案等于多点最近公共祖先的深度。我们先用单调栈求出左右第一个更大位置，从而构造最大笛卡尔树。然后使用倍增预处理最近公共祖先。每次询问依次合并所有选定星球的 LCA，最终输出所得节点的深度。从单个机器人的可达位置开始对于星球

i

，记：

L\_i

为左边第一个满足

p\_{L\_i}>p\_i

的位置。

A\_{i,j}\subseteq A\_{i,j-1},

为右边第一个满足

p\_{R\_i}>p\_i

的位置。

如果对应位置不存在，就暂时记为

0

。题目中的自环不会产生新的可达星球，因此分析可达范围时可以忽略自环。如果直接按照传送门搜索，一个机器人最多可能经过

O(n)

个星球。所有询问中一共给出

m

个起始星球，因此最坏复杂度会达到

O(nm),

无法通过

5\times 10^5

的数据范围。问题的关键在于，这张有向图并不是一般的有向图。每次非自环移动都会到达一个大小更大的星球，因此不存在由多个不同星球组成的有向环。更重要的是，左右第一个更大元素正好对应笛卡尔树中的祖先关系。为什么会想到最大笛卡尔树最大笛卡尔树是一棵满足以下条件的二叉树：

中序遍历节点的顺序为

1,2,\ldots,n

。

每个父节点的权值都大于它的子节点。

因为

p

是一个排列，所以所有权值不同，这棵笛卡尔树唯一。笛卡尔树经常用于处理“左侧第一个更大”“右侧第一个更大”和“区间最大值”之间的关系。本题的两个传送门恰好就是左右第一个更大位置，因此可以尝试研究它们与笛卡尔树父亲之间的关系。确定笛卡尔树中的父亲对于节点

i

，它在最大笛卡尔树中的父亲可以由

L\_i

和

k=0

确定。如果只有一个位置存在，那么这个位置就是

i

的父亲。如果两个位置都存在，那么父亲是二者中权值较小的那个：$ \operatorname{fa}*i= \begin{cases} L\_i, & R\_i=0,\\ R\_i, & L\_i=0,\\ L\_i, & p*{L\_i}\<p\_{R\_i},\\ R\_i, & p\_{R\_i}\<p\_{L\_i}. \end{cases} $假设

L\_i

和

R\_i

都存在，并且

x=n-1,

由于

L\_i

是左边第一个更大的位置，所以区间

(L\_i,i)

中的所有权值都小于

p\_i

。由于

R\_i

是右边第一个更大的位置，所以区间

w\_i

中的所有权值也都小于

p\_i

。因此在整个区间

x

中：

R\_i

的权值最大。

L\_i

的权值仅次于

R\_i

。

i

的权值大于两个端点之间的其他所有位置。

所以在这个区间对应的笛卡尔树结构中，

R\_i

位于

L\_i

上方，而

i

直接成为

L\_i

的子节点。因此

w\_{i+1}

的父亲是

L\_i

，也就是两个候选位置中权值较小的那个。另一种大小关系完全对称。传送门与祖先的关系现在研究星球

i

的两个传送门。若

L\_i

和

i-1

都存在，其中权值较小的节点是

i

的父亲，权值较大的节点位于父亲上方，因此二者都是

i

的祖先。若只有一个位置存在，这个位置就是

i

的父亲。若某个方向不存在更大元素，对应传送门是自环，不会增加新的可达位置。所以每次使用非自环传送门，机器人都会从当前节点移动到笛卡尔树中的某个祖先。因此，一个机器人能够到达的位置不会超出它的祖先链。另一方面，每个节点的父亲一定是两个传送门之一。机器人可以不断使用指向父亲的传送门，从当前节点依次到达父亲、祖父以及更高的祖先。所以从节点

i

出发的可达集合恰好为

\operatorname{Reach}(i)=\operatorname{Anc}(i),

其中

\operatorname{Anc}(i)

表示包含

i

自身在内的全部祖先。多个机器人的共同可达点设一次询问选择的节点为

x\_1,x\_2,\ldots,x\_k.

机器人能够在节点

v

汇合，当且仅当

v

是每个

x\_i

的祖先。因此所有可能的汇合点组成集合$ \operatorname{Anc}(x\_1) \cap \operatorname{Anc}(x\_2) \cap\cdots\cap \operatorname{Anc}(x\_k). $设这些节点的最近公共祖先为

g=\operatorname{LCA}(x\_1,x\_2,\ldots,x\_k).

树中一组节点的所有公共祖先，恰好是它们最近公共祖先

g

的全部祖先。因此共同可达点集合为

\operatorname{Anc}(g).

如果令根节点深度为

1

，那么一个节点的祖先数量恰好等于它的深度，所以本次询问的答案为

\operatorname{dep}\_g.

如何计算多点 LCA倍增算法通常计算两个节点的最近公共祖先。多点最近公共祖先可以逐个合并：

g\_1=x\_1,

g\_i=\operatorname{LCA}(g\_{i-1},x\_i).

处理完全部

k

个节点后，

g\_k

就是所有选定节点的最近公共祖先。这样一次询问需要进行

k-1

次普通 LCA 查询。所有询问中的节点总数为

m

，因此查询部分的总复杂度为

O(m\log n).

算法流程

读入 $n,q$ 和排列 $p$ 。

从左向右扫描排列，维护一个权值严格递减的单调栈。

对于每个位置 $1\<d\<n$ ，弹出所有权值小于 $p\_i$ 的位置。弹栈完成后的栈顶就是 $L\_i$ 。如果栈为空，则 $L\_i=0$ 。

从右向左进行同样的扫描，求出每个位置的 $R\_i$ 。

根据 $L\_i$ 和 $R\_i$ 确定父亲：

如果二者都不存在， $i$ 是笛卡尔树的根。
如果只有一个存在，父亲就是这个位置。
如果二者都存在，选择权值较小的位置作为父亲。

从父亲向儿子连边，构造有根树。

从根节点开始进行广度优先遍历：

根节点深度设为 $1$ 。
记录每个节点的直接父亲。
预处理倍增数组 $up_{j,i}

113 浏览2 点赞0 收藏1 评论

P1850 [NOIP 2016 提高组] 换教室

YIZHIYANG初来乍到 2026-7-5 8:06:05

#算法

P1850 [NOIP 2016 提高组] 换教室知识点Floyd 最短路 + 概率期望 + 动态规划题意概括牛牛每节课原本在教室

c_i

，可以申请换到教室

d_i

。第

2,3,\ldots,\lfloor\sqrt n\rfloor.

节课申请成功的概率为

k_i

，最多申请

a

节课。需要选择申请哪些课程，使相邻课程教室之间最短路长度总和的期望最小。解题思路首先，牛牛在两个教室之间一定选择体力消耗最小的路径，因此使用 Floyd 算法求出任意两个教室之间的最短距离。接下来考虑动态规划。申请第

i

节课程后，实际上课教室有两种可能：

以

1-k_i

的概率在教室

c_i

；

以

k_i

的概率在教室

d_i

。

相邻两节课之间的期望距离，只和这两节课是否申请有关，与更早的选择无关。因此可以将当前课程是否申请作为状态。设：

f_{j,0}

表示处理完当前课程，共申请了

j

节，并且当前课程没有申请时的最小期望体力值。设：

f_{j,1}

表示处理完当前课程，共申请了

j

节，并且当前课程申请了时的最小期望体力值。下面考虑从第

i-1

节课转移到第

i

节课。当前课程不申请当前课程一定在教室

c_i

。如果上一节课也没有申请，上一节课一定在教室

c_{i-1}

，新增体力值为：

dis(c_{i-1},c_i)

对应转移为：

f_{j,0}+dis(c_{i-1},c_i)

以

1-k_{i-1}

的概率在教室

c_{i-1}

；

以

k_{i-1}

的概率在教室

d_{i-1}

。

新增期望体力值为：对应转移为：两种情况取最小值。当前课程申请当前课程有两种可能：

以

1-k_i

的概率在教室

c_i

；

以

k_i

的概率在教室

d_i

。

c_{i-1}

，新增期望体力值为：

(1-k_i)dis(c_{i-1},c_i) +k_i dis(c_{i-1},d_i)

对应转移为：如果上一节课也申请了，那么相邻两节课分别有两种可能，共有四种组合。新增期望体力值为：对应转移为：由于每一层只依赖上一层，可以使用滚动数组将空间复杂度降为

O(m)

。最后枚举申请数量

0

到

m

。题目要求至多申请

m

节，因此答案是所有合法状态的最小值，而不是只计算恰好申请

m

节的情况。参考代码/* 题意：最多申请更换 m 节课，每次申请有独立的成功概率，求相邻课程教室间最短路长度总和的最小期望。思路：先用 Floyd 求任意教室间最短路。设 f[j][0/1] 表示处理完当前课程，申请 j 次，且当前课程不申请或申请时的最小期望。根据相邻两节课是否申请，计算两种或四种位置组合的期望。使用滚动数组优化空间。 */ #include<bits/stdc++.h> using namespace std; using ll=long long; const int N=2005; const int V=305; const int inf=1e9; const double INF=1e100; int c[N],d[N],g[V][V]; double k[N],f[N][2],h[N][2]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m,v,e; cin>>n>>m>>v>>e; m=min(m,n); for(int i=1;i<=n;i++) cin>>c[i]; for(int i=1;i<=n;i++) cin>>d[i]; for(int i=1;i<=n;i++) cin>>k[i]; for(int i=1;i<=v;i++){ for(int j=1;j<=v;j++){ g[i][j]=(i==j?0:inf); } } while(e--){ int a,b,w; cin>>a>>b>>w; g[a][b]=min(g[a][b],w); g[b][a]=min(g[b][a],w); } for(int t=1;t<=v;t++){ for(int i=1;i<=v;i++){ for(int j=1;j<=v;j++){ g[i][j]=min(g[i][j],g[i][t]+g[t][j]); } } } for(int j=0;j<=m;j++){ f[j][0]=INF; f[j][1]=INF; } f[0][0]=0; if(m) f[1][1]=0; for(int i=2;i<=n;i++){ for(int j=0;j<=m;j++){ h[j][0]=INF; h[j][1]=INF; } int up=min(i,m); for(int j=0;j<=up;j++){ h[j][0]=min( f[j][0]+g[c[i-1]][c[i]], f[j][1]+(1-k[i-1])*g[c[i-1]][c[i]] +k[i-1]*g[d[i-1]][c[i]] ); if(!j) continue; h[j][1]=min( f[j-1][0]+(1-k[i])*g[c[i-1]][c[i]] +k[i]*g[c[i-1]][d[i]], f[j-1][1] +(1-k[i-1])*(1-k[i])*g[c[i-1]][c[i]] +(1-k[i-1])*k[i]*g[c[i-1]][d[i]] +k[i-1]*(1-k[i])*g[d[i-1]][c[i]] +k[i-1]*k[i]*g[d[i-1]][d[i]] ); } for(int j=0;j<=m;j++){ f[j][0]=h[j][0]; f[j][1]=h[j][1]; } } double ans=INF; for(int j=0;j<=m;j++){

102 浏览0 点赞0 收藏0 评论

精华

普通平衡树

YIZHIYANG初来乍到 2026-6-7 12:03:39

#include<bits/stdc++.h> using namespace std; using ll = long long; const int N = 100005; int n, rt, tot; int ch[N][2], sz[N], va[N]; unsigned ky[N], sd = 71236721; unsigned rd() { sd ^= sd << 13; sd ^= sd >> 17; sd ^= sd << 5; return sd; } int nw(int v) { ++tot; va[tot] = v; sz[tot] = 1; ky[tot] = rd(); return tot; } void pu(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1; } void sp(int u, int v, int &x, int &y) { if (!u) { x = y = 0; return; } if (va[u] <= v) { x = u; sp(ch[u][1], v, ch[u][1], y); pu(x); } else { y = u; sp(ch[u][0], v, x, ch[u][0]); pu(y); } } int mg(int x, int y) { if (!x || !y) return x + y; if (ky[x] < ky[y]) { ch[x][1] = mg(ch[x][1], y); pu(x); return x; } else { ch[y][0] = mg(x, ch[y][0]); pu(y); return y; } } void ins(int v) { int a, b; sp(rt, v, a, b); rt = mg(mg(a, nw(v)), b); } void del(int v) { int a, b, c; sp(rt, v, a, c); sp(a, v - 1, a, b); if (b) b = mg(ch[b][0], ch[b][1]); rt = mg(mg(a, b), c); } int kth(int u, int k) { while (1) { int lz = sz[ch[u][0]]; if (k <= lz) u = ch[u][0]; else if (k == lz + 1) return va[u]; else { k -= lz + 1; u = ch[u][1]; } } } int rk(int v) { int a, b; sp(rt, v - 1, a, b); int an = sz[a] + 1; rt = mg(a, b); return an; } int pre(int v) { int a, b; sp(rt, v - 1, a, b); int an = kth(a, sz[a]); rt = mg(a, b); return an; } int nxt(int v) { int a, b; sp(rt, v, a, b); int an = kth(b, 1); rt = mg(a, b); return an; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; while (n--) { int op, x; cin >> op >> x; if (op == 1) ins(x); else if (op == 2) del(x); else if (op == 3) cout << rk(x) << "\n"; else if (op == 4) cout << kth(rt, x) << "\n"; else if (op == 5) cout << pre(x) << "\n"; else cout << nxt(x) << "\n"; } return 0; }

107 浏览1 点赞0 收藏0 评论

精华

文艺平衡树

YIZHIYANG初来乍到 2026-6-7 10:32:24

// Problem: P3391 【模板】文艺平衡树 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P3391 // Memory Limit: 125 MB // Time Limit: 1000 ms // by 1zhio2 // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; using ll = long long; const int N = 100005; int n, m, rt, tot; int ch[N][2], sz[N], va[N], ky[N], tg[N]; mt19937 rnd(71236721); int nw(int v) { ++tot; va[tot] = v; sz[tot] = 1; ky[tot] = rnd(); return tot; } void pu(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1; } void rv(int x) { if (!x) return; swap(ch[x][0], ch[x][1]); tg[x] ^= 1; } void pd(int x) { if (!tg[x]) return; rv(ch[x][0]); rv(ch[x][1]); tg[x] = 0; } void sp(int u, int k, int &x, int &y) { if (!u) { x = y = 0; return; } pd(u); int lz = sz[ch[u][0]]; if (k <= lz) { y = u; sp(ch[u][0], k, x, ch[u][0]); pu(y); } else { x = u; sp(ch[u][1], k - lz - 1, ch[u][1], y); pu(x); } } int mg(int x, int y) { if (!x || !y) return x + y; if (ky[x] < ky[y]) { pd(x); ch[x][1] = mg(ch[x][1], y); pu(x); return x; } else { pd(y); ch[y][0] = mg(x, ch[y][0]); pu(y); return y; } } void dfs(int x) { if (!x) return; pd(x); dfs(ch[x][0]); cout << va[x] << " "; dfs(ch[x][1]); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) rt = mg(rt, nw(i)); while (m--) { int l, r; cin >> l >> r; int a, b, c, d; sp(rt, l - 1, a, b); sp(b, r - l + 1, c, d); rv(c); rt = mg(a, mg(c, d)); } dfs(rt); return 0; }

107 浏览2 点赞0 收藏0 评论

YIZHIYANG 的动态

P12544 [UOI 2025] Boys and Girls

思路

关键性质

情况 1：所有边经过同一个点

情况 2：三角形

三角形枚举

复杂度

C++代码

【排序 + 状态压缩背包】掷出重围

关键性质

朴素动态规划

状态定义

投出当前球

将基准移动到下一个落点

正确性说明

参考实现

复杂度分析

【独立计数，快速幂】P6075 子集选取

题意概括

样例分析

算法思路

不同元素相互独立

每一行都是一个前缀

统计前缀长度序列

f_{i,j}

计算总答案

算法流程

正确性说明

实现细节与易错点

参考实现

复杂度分析

ABC468F Chmax

关键性质

1. 遇到新的前缀最大值

2. 遇到不是前缀最大值的数

举例

C++14 代码

解题思路

Miller-Rabin 与 Pollard-Rho

一、为什么普通质因数分解不够

二、Miller-Rabin 判素数

1. 从费马小定理开始

2. 拆分 n−1n-1n−1

3. 检验过程

4. 为什么要检查 n−1n-1n−1

5. 646464 位整数的固定底数

三、Pollard-Rho 找因子

1. 构造伪随机序列

2. 为什么能找到因子

3. Floyd 判环

d=1d=1d=1

1\<d\<n1\<d\<n1\<d\<n

d=nd=nd=n

四、完整分解过程

五、C++14 模板

【最大笛卡尔树，倍增 LCA】传送

题意概括

样例分析

算法思路

整体思路

从单个机器人的可达位置开始

为什么会想到最大笛卡尔树

确定笛卡尔树中的父亲

传送门与祖先的关系

多个机器人的共同可达点

如何计算多点 LCA

算法流程

P1850 [NOIP 2016 提高组] 换教室

知识点

题意概括

解题思路

当前课程不申请

当前课程申请

参考代码

登录

2. 拆分 $n-1$

4. 为什么要检查 $n-1$

5. $64$ 位整数的固定底数

$d=1$

$1\<d\<n$

$d=n$