DUMBLOG

洛谷题目链接
Acwing题目链接

思路

先预处理出最近和次近的城市，记录下每次循环后所在城市的位置，然后倍增处理。

背景

给定一张带负权边的有向无环图（DAG），$N$ 个点，$M$ 条边，求源点到各点的最短路。

分析

因为有负权边，无法用 dijkstra 直接求最短路。

用 SPFA 又容易被出题人卡成傻子。

考虑到是 DAG，可以使用拓扑排序在 $O(N+M)$ 时间范围内求出最短路。

已经是22年了捏。

！！！🏮新年好🏮！！！

Dumby_cat 隆重推出 Dumblog 新年款！！！（其实就是变红了。。。）

总之，祝各位来访者新年快乐！！！

加法及乘法原理

加法原理

完成一件事有 $n$ 类方法，每类方法有 $m$ 个不同的方法，那么完成这件事总共就有 $N=m_1+m_2+\dots +m_n$ 种方法。

题目描述

试求出：

$\lceil {\left(\frac{1+\sqrt{5}}{2}\right)}^n\rceil mod998244353$

多测

洛谷P3263

题意描述

给定 $b$、$d$ 和 $n$。

试求出：

$\lfloor {\left(\frac{b+\sqrt{d}}{2}\right)}^n\rfloor modp$

题目链接

并查集是甚么

并查集（Disjoint-set data structure），直译为 “不交集数据结构”，顾名思义，它是种数据结构。并且，它是种用来处理 不交集（不相交集合）的合并和查询问题 的数据结构。
并查集维护的是元素之间的关系。

背景

关于快速幂：
它死了。
咳咳。

定义

1 到 $N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\phi (N)$。

函数式

$\phi \left(n\right)=n\times \prod _{i=1}^m(1-\frac{1}{p_i})$