题目列表

先写出原题的 O(nk) 计数 DP，再把状态改写成第二类 Stirling 数，最后用满射计数的容斥公式在线性预处理后求出 S(n,n-k)。

先算每种做法任选或不选的总方案数，再按食材枚举严格多数者，用差值 DP 统计坏方案并从总数中扣掉。

先预处理 4 种硬币无限使用时的完全背包方案数，再对每个询问用 16 个子集做容斥，扣掉任意一种硬币超上界的方案。

先算完整 n×m 网格所有出生点对的曼哈顿距离和，再减去所有涉及障碍点的贡献，最后补回障碍之间被多减的一次。

先统计每个 t 的倍数里有多少齿轮，再用 C(cnt[t],k) 算 gcd 是 t 的倍数的方案数，最后按倍数从大到小容斥还原精确 gcd。

把每种金属在 k 个熔炉中的出现情况看成一个长度为 k 的 0/1 模式，合法模式有 2^k-1 种，总答案是 (2^k-1)^n。

先算总状态数 m^n，再减去所有相邻房间宗教都不同的安全状态数 m·(m-1)^(n-1)。

把每轮操作看成当前酒量加上 b 再对 a 取模，最小正体积就是 gcd(a,b)，再用 exgcd 求 b·y-a·x=g 的最小正解。

付款方做有限硬币最少张数 DP，找零方做无限硬币最少张数 DP，再枚举实付金额取最优。

如果 n mod 1..m 没有重复，那么它们只能依次是 0,1,2,...,m-1，等价于 1..m 全都整除 n+1。

设恰好 p 个人抽到最大记号数 t，则总记号数必须落在 [p t, p t + (n-p)(t-1)]，找到合法 t 后再贪心构造。

先预处理每个格子最近球员的到达代价，再把空球、控球和四个踢球方向建成 6 层状态图跑最短路。

把原式改写成 |(a+bi)(p-qi)+(c+di)(r+si)|^2，在高斯整数环里用扩展欧几里得求 gcd 和贝祖系数。

先用 exgcd 求 ax+by=-c 的一组特解，再把通解写成 x=x0+k·b/d, y=y0-k·a/d，把矩形范围限制都转成对 k 的区间约束，最后求区间交集大小。

先用 exgcd 判断 ax+by=c 是否有整数解，再把通解写成 x=x0+k·b/d, y=y0-k·a/d，通过不等式求出正整数解对应的 k 范围。

把两只青蛙第 t 次跳跃后位置相等写成 (m-n)t≡y-x(mod L)，再用扩展欧几里得求最小非负解；若 gcd(m-n,L) 不能整除 y-x，则无解。

把 ax≡1(mod b) 改写成 ax+by=1，用扩展欧几里得求出一组解，其中 x 在模 b 意义下的最小正值就是答案。

设 f[i] 表示杀死一只 i 号怪兽的最小体力，满足 f[i]=min(K_i, S_i+Σf[spawn])。先把法术攻击代价当作初值，再从已确定更小代价的子怪兽反向更新父怪兽。

对每个城市分别维护“机器人最早能到城门的时间”和“所有前置发生器最晚被摧毁的时间”，城市真正被摧毁的时间是这两者的最大值，再用 Dijkstra 式过程按时间推进。

把状态定义成“当前所在牧场 + 已改造道路数”。走一条边时要么正常付边权，要么消耗一次改造机会把这条边代价降成 0，在状态图上跑 Dijkstra。

把状态定义成"当前所在城市 + 已用卡数"。走一条边时要么正常通过，要么额外消耗一张卡把这条边代价减半，在这个状态图上跑 Dijkstra。

把每个关键交点拆成“横线状态”和“竖线状态”两个点；同一条线上的相邻关键点连边，换乘站内部连一条代价为 1 的边，再在这张图上跑最短路。

按牧场过路费从小到大加入 Floyd 中转点，维护边权和最短路；每次加入新中转点后，用“边权和 + 当前允许最大点权”更新所有点对答案。

先求出一条 1 到 N 的最短路。只有这条路上的边被封闭才可能让答案变大，因此依次禁用这些边并重跑最短路取最大值。

把已有电线当成 0 权边，把距离不超过 M 的点对当成可补的新边，在这张图上跑最短路求从 1 到 N 的最小补线长度。

先 Floyd 求每个连通块内任意两点最短路，再枚举跨块连边，用两端点到各自块内最远点的距离更新合并后的最小直径。

先求出一条从 1 到 N 的最短路。只有这条路上的边加倍后才可能让答案变大，因此枚举这条路上的每条边临时加倍，再重跑 Dijkstra 取最短路增量最大值。

只需要比较两种送货顺序：PB->PA1->PA2 和 PB->PA2->PA1。图是无向图，因此求出 PB 到两点的距离和 PA1 到 PA2 的距离后即可直接取最小值。

所有奶牛都要判断能否在 M 秒内到达同一个目标点 1，所以只需从 1 号草地做一次 Dijkstra，再按奶牛编号检查距离是否不超过 M。

这是无权图单源最短路。先从 1 号点做 BFS，得到每个点的最短层数，再统计最远距离、最小编号和该距离出现次数。

这题不是最短路求和，而是最小化路径上的最大边权；点数只有 300，可以直接用 Floyd 的 min-max 转移求所有点对的最小瓶颈路。

牧场总数只有 52 个，把大小写字母映射成编号后直接 Floyd 求全源最短路，再在 A..Y 中找离 Z 最近的那头牛。

往返距离等于 i 到 x 再加 x 到 i；原图从 x 跑一次 Dijkstra，反图再从 x 跑一次 Dijkstra，就能得到所有点的来回最短路。

标准正权无向图单源最短路，直接从起点 s 跑一次 Dijkstra，输出到终点 t 的距离即可。

路线被强制经过 1 号牧场，所以先从 1 号点跑一次 Dijkstra，任意询问答案都是 dist[p] + dist[q]。

利用无向图距离对称性，从每个喜欢的牧场各跑一次 Dijkstra，把到所有点的距离累加后取总和最小的牧场。

路径加可以先做树上差分，再把子树和展开成 diff 的加权求和；结合 LCA、DFS 序和两棵树状数组，就能在线维护路径加与子树和查询。

两点间最优通信稳定性等于所有路径中最小边权的最大值，这正是最大生成森林上的路径最小边权；先 Kruskal 建最大生成森林，再用倍增 LCA 查询路径最小边。

对每个节点预处理根到它路径上的 depth^k 前缀和，再用 LCA 把路径拆成两段：sum(x)+sum(y)-2sum(lca)+depth(lca)^k。

商人的总路程就是从首都出发后，相邻两站之间树上距离的总和；用倍增 LCA 快速求两点距离，再顺着给定路线累加即可。

把每台电脑的度数看成点权，询问就是树上两点路径点权和；预处理根到每个点的前缀和，再用 LCA 把路径拆成两段即可。

一组员工都能被同一人管理，等价于这个人是他们的公共祖先；先求这组点的 LCA，再在根到该 LCA 的路径上取最大编号即可。

封锁一个点后，真正新增损失来自它把图切成的多个连通块；用 Tarjan 求割点时顺手统计每个被切下来的子树大小，就能在线性时间算出每个点造成的访问损失。

把每个兴奋值看成一个状态值，若某个兴奋值 x 能选择一个结束兴奋值为 y 的游戏，就连边 x->y；某个游戏能玩两次，当且仅当它的 e_i 能回到某个整除 w_i 的同 SCC 状态。

关键线路一定是桥；先用 Tarjan 找桥，再统计桥两侧是否都同时含有 A、B 两种服务，只要某一侧缺少其中一种服务，这条桥就是答案。

先把同高且连通的格子缩成强连通块，块间只能从高处指向低处，缩点后是一张 DAG，最少缆车数就是入度为 0 的块数与出度为 0 的块数的较大值。

Tarjan 回溯时若树边 u-v 满足 low[v] >= dfn[u]，说明 v 子树必须经过 u 才能连到外部，此时把点栈弹到 v 再加上 u，就得到一个点双连通分量。

在无向图上跑一遍 Tarjan，若某个儿子 v 满足 low[v] >= dfn[u]，就说明删掉 u 会让这棵子树断开；根节点还要单独判断子树个数。

先用 Tarjan 找出无向图中的所有桥，再把这些桥删掉，剩下的每个连通块就是一个边双连通分量。

把无向图做一遍 Tarjan，若树边 u-v 满足 low[v] > dfn[u]，说明 v 子树回不到 u 及其祖先，这条边就是桥。

先求从 1 号景点出发能到达的全部景点；在这些点上按边的较低端高度降序、边长升序做 Kruskal，可以在保证可达景点数最大的前提下，把总滑行距离压到最小。

二分最大允许造价 T。对每个 T，只看二级造价不超过 T 的边是否能连通全图，再看一级造价不超过 T 的边最多能提供多少条一级公路，从而判断可行性。

每周只新增一条边，因此当前最小生成树只可能通过“接上一条新边”或“用新边替换环上的更大边”发生变化；维护最小生成森林即可在线输出答案。

先用 BFS 求出任意两座城市之间的最短骑士步数，再把“从已占领城市攻占一座新城市”的代价视作边权，整道题就转化成一棵最小生成树。

题面按轮修路的过程本质是在构造欧几里得最小生成树，最终总长度就等于 MST 边长之和；点数较大时直接用 Prim 求解即可。

这是带门槛的最小生成树：只有距离平方不小于 c 的边允许使用，直接在完全图上做 Prim，若中途出现不可达点则答案不存在。

要求把 N 个点连成恰好 K 个连通块且总代价最小，本质就是最小生成森林；按边权从小到大做 Kruskal，连到只剩 K 个连通块时停止。

把“原价买一件礼物”看成从虚拟源点连一条权值 A 的边，把优惠价看成礼物之间的边权，原题就转化成一棵最小生成树。

要求先用最少的边把全图连通，因此一定选 n-1 条边；再把这些边中的最大权值压到最小，直接按边权从小到大做 Kruskal，最后一条加入的边权就是答案。

把两棵树之间能否跳过去看成边，所有树都能互达所需的最小跳距，等于一棵最小生成树中的最大边长；用 Prim 求出这个临界值后统计能达到的猴子数量。