文章

// 标题是糊弄人的 1. 问题引入 给出一张图，求其最短哈密尔顿回路，也就是 “旅行商问题”（Traveling Saleman Problem，TSP）假设有一个旅行商人要拜访 $n$个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。 路径的选择目 阅读更多…

听说是权限题所以没有传送门 题意大概是说给你 $n$个队员的年龄和水平值，每次询问选 $k$个小于等于年龄 $a$的队员的最大水平值和为多少。要求每次选择队员水平值不能相邻（指它们的水平值的 $rank$不相邻）首先可以考虑离线降维，我们将年龄从小到大排个序，是队员就加入待选，是询问就在待选队员里 阅读更多…

题目分析 题目要求 $x^A \equiv B \pmod{P}$的解的个数。 首先将 $P$分解质因数，对于每个方程 $x^A \equiv b_i \pmod{p_i^{a_i}}$，求出解的个数。假设我们确定了这个方程的解，最后用中国剩余定理合并，不同方程组肯定对应不同的解，所以将每个方程的解 阅读更多…

Cipolla 问题 给定 $n​$, 在模 $p​$意义下求 $x​$，使得 $x^2\equiv n \pmod p​$。其中 $p​$是一个奇素数。 原理 为了解决这个问题，我们首先需要知道以下几个定理。 定理 1： 使得 $x^2\equiv n \mod p​$有解的 $n​$在 $[0, 阅读更多…

题目分析 构造邻接矩阵 $G$，要求的是 $\sum_{i=0}^n C_n^iG^i [k|i]$ 单位根反演嘛，$\frac{1}{k}\sum_{i=0}^{k-1} \omega_k^{in}=[k|n]$。 $$\sum _ {i=0}^n C _ n^iG^i[k|i]=\frac{1} 阅读更多…

传送门 这道题比较神仙所以我来写篇 blog 记录下 qwq 首先它让我们求的是 $$\sum_{L\leq i<j\leq R}gcd(a[i],a[j])$$ 我刚开始是想到 $gcd$是具有差分不变的性质，但是这似乎只能转化区间呀所以没啥用 后来想记录因数来统计，可是感觉要容斥搞半天就自 阅读更多…

题目分析 听说是个 DP 经典套路？ 令 $f(i)$表示 $i$个一样的连在一起的元素，被消完的最大分数，一个完全背包可以搞定。 然后将连续的一段相同元素合成一个点，原序列变成了若干黑白交错的点，记点 $i$中的元素个数为 $sz(i)$。 令 $g(l,r,k)$表示现在要消完 $[l,r]$这 阅读更多…

题目链接 题目大意： 给一个整点多边形，求其面积、多边形上整点数目、多边形内整点数目（数据是按 $\Delta x, \Delta y$给出的）点数和 $|\Delta |$$\leq 100$ 这题就是皮克定理的模板题啦！ 皮克定理英文名：Pick’s theorem 定理内容： 阅读更多…

定理内容 对于二分图中的集合 $X$和 $Y$（$|X| \leq |Y|$），任取一个 $X$的子集 $s$（$s \subseteq X$），设 $Y$中与 $s$有边相连的点集为 $N(s)$，若 $X$和 $Y$存在完美匹配（完美匹配指的是匹配数 $= |X|$），则一定满足 $|s| \l 阅读更多…

传送门 题目大意：求满足以下式子的 $1\leq n\leq x$的个数 $$n\cdot a^n=b\; (mod\;p)$$ 其中 $a,b,p \leq 10^6,x \leq 10^{12}$ 老年选手不会推式子系列.jpg 首先我们根据费马小定理，显然可以对 $n$做带余除法 $n=(p- 阅读更多…