Q779’s Blog

洛谷P4213 【模板】杜教筛 题解 题目链接：P4213 【模板】杜教筛 题意： 给定一个正整数，求 \[ \mathrm{ans}_1=\sum_{i=1}^n\varphi(i) \\[4pt]\mathrm{ans}_2=\sum_{i=1}^n \mu(i) \] 输入格式： 本题有多组数据。 输入的第一行为一个整数，表示数据组数 \(T\)。 接下来 \(T\) 行，每行一个整数 \(n\)，表示一组询问。 输出格式： 对于每组询问，输出一行两个整数，分别代表 \(\mathrm{ans}_1\) 和 \(\mathrm{ans}_2\)。 数据范围： 对于全部的测试点，保证 \(1 \leq T \leq 10\)，\(1 \leq n \lt 2^{31}\)。 杜教筛是一种能在非线性时间内求解积性函数的前缀和的算法。 设 \(S(n) = \sum_{i=1}^{n} f(i)\) ，其中 \(f\) 为积性函数。另设积性函数 \(g\) ，考虑他们的狄利克雷卷积的前缀和 \[ \begin{aligned} \sum_{i = 1}^n (f * ...

欧拉反演 前言：因为一直记错这个东西，所以来写一下。 欧拉反演 \[ \mathrm{id}=\varphi * \mathbf{1}\Longleftrightarrow n=\sum_{d \mid n} \varphi(d) \] 其中 \(*\) 是狄利克雷卷积。参考 生成函数 学习笔记 。 例：证明下式 \[ \sum_{i=1}^n \gcd(i, n)=\sum_{d \mid n} \frac{n}{d} \varphi(d) \] 证明 根据引理有 \[ \gcd(i,j) = \sum_{d \mid \gcd(i,j)}\varphi(d) = \sum_{d\mid i}\sum_{d \mid j} \varphi(d) \] 那么 \[ \begin{aligned} \sum_{i=1}^n \gcd(i, n) &= \sum_{i=1}^n\sum_{d\mid i}\sum_{d \mid n} \varphi(d) \\[6pt] &=\sum_{d \mid n} \sum_{i=1}^n\sum_{d\mid i} \...

洛谷P8347 「Wdoi-6」另一侧的月 题解 题目链接：P8347 「Wdoi-6」另一侧的月 题意： 给定 \(n\) 个节点的树（保证 \(n\ge 2\)），Hifuu 和 Luna 交替操作，前者先手。每回合操作者选择一个节点，将「该节点」和「所有与该节点相连的边」删除，形成若干个连通块，操作者再从中保留一个连通块。如果该回合结束后只剩下一个节点，则该回合的操作者失败，另一个人胜利。问谁存在必胜策略。 输入格式： 本题多组数据。第一行输入一个正整数 \(T\)，表示数据组数。对于每一组数据： 第一行有一个正整数 \(n\)。 接下来 \(n-1\) 行，每行两个正整数 \(u_i,v_i\)。表示一条连接节点 \(u_i\) 和 \(v_i\) 的双向的灵能输送渠道。 输出格式： 对于每一组数据，输出莲子和梅莉是否能够到达月之都。具体而言，若她们存在必定能到达月之都的策略，则输出 \(\texttt{Hifuu}\)，否则输出 \(\texttt{Luna}\)。 数据范围： \(1 \leq T \leq 5\)，\(2 \le n \le 10^5\)，输入...

洛谷P5363 [SDOI2019] 移动金币 题解 题目链接：P5363 [SDOI2019] 移动金币 题意： Alice 和 Bob 将要进行如下的一场游戏。二人轮流操作，且 Alice 先行。 当轮到一个玩家的时候，他可以选择一枚金币，并将其向左移动任意多格，且至少移动一格。金币不能被移出棋盘，也不能越过其它金币。 一个 \(1\times n\) 的棋盘上最初摆放有 \(m\) 枚金币。其中每一枚金币占据了一个独立的格子，任意一个格子内最多只有一枚金币。 如果轮到一个玩家的时候他已经无法做出任何有效操作了（显然这个时候 \(m\) 枚金币恰好落在最左侧的 \(m\) 个格子中），则被判定为输家。已经知道 Alice 和 Bob 都是极致聪明的人，他们在任何局面下总能做出最优的操作。那么有多少初始状态能保证 Alice 必胜呢？ 输入格式： 输入仅有一行并包含两个正整数，依次为 \(n\) 和 \(m\)，如题目所述。 输出格式： 输出一个整数，表示有多少初始状态可以保证 Alice 作为先手方能先手必胜。 由于答案可能很大，请输出关于 \(10^9+9\) 取模后的值...

洛谷P10507 Georgia and Bob 题解 题目链接：P10507 Georgia and Bob 题意： 有一个无限长的棋盘，从左到右编号为 \(1,2,3,\cdots\)。有 \(n\) 个棋子在棋盘上，定义一次操作为把一枚棋子向左移动至少一格，不可以逾越其他棋子，不可与其他棋子重合，不可移出棋盘。 告诉你这 \(n\) 个棋子的位置（不保证顺序且保证没有棋子重合），Georgia 和 Bob 轮流进行操作，Georgia 先手，谁无法操作谁输。问最后谁会赢？ 输入格式： 本题有多组数据。 第一行一个整数 \(T\)，表示数据组数。 对于每组数据： 第一行一个整数 \(n\)。 接下来一行 \(n\) 个整数，表示每个棋子的位置。 输出格式： 对于每组数据，若 Georgia 胜输出 Georgia will win，若 Bob 胜输出 Bob will win。 首先对 \(x_i\) 排序，记 \(b_i = x_i - x_{i-1}-1\) 是每个棋子初始可以移动的格数。 注意到当第 \(i\) 个棋子移动 \(x\) 格时，会使得 \(b_i \...

洛谷P3480 [POI2009] KAM-Pebbles 题解 题目链接：P3480 [POI2009] KAM-Pebbles 题意： 有 \(N\) 堆石子，除了第一堆外，每堆石子个数都不少于前一堆的石子个数。 两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足初始时的条件。 谁没有石子可移时输掉游戏。问先手是否必胜。 输入格式： 多组输入，第一行一个整数 \(u\) 代表数据组数（\(1\le u\le 10\)） 接下来共 \(2u\) 行，每两行代表一组数据： 第一行只有一个整数 \(n~(1\le n\le 1000)\)，表示石子堆数； 第二行有 \(n\) 个整数用空格隔开，第 \(i\) 个整数 \(a_i\) 表示第 \(i\) 堆的石子个数，保证 \(a_1\le a_2\le a_3\le \cdots\le a_n\)。 对于每组数据，保证石子总数不超过 \(10000\)。 输出格式： 输出 \(u\) 行，如果第 \(i\) 组数据先手必胜，输出 TAK，否则输出 NIE。 设 \(a_i\) 为第 \(i\) 堆石子...

[AGC002E] Candy Piles 题解 题目链接：[AGC002E] Candy Piles 题意： 桌上有 \(n\) 堆糖果，第 \(i\) 堆糖果有 \(a_i\) 个糖。 两人在玩游戏，轮流进行，每次进行下列两个操作中的一个: 将当前最大的那堆糖果全部吃完； 将每堆糖果吃掉一个； 吃完的人输，假设两人足够聪明，问谁有必胜策略？ 输出 First（表示先手必胜）或 Second（表示后手必胜） 数据范围： \(1\leq n\leq10^5,~1\leq a_i\leq10^9\) 考虑对这些石子堆降序排序，如下图所示 那么每次操作就变成了 于是原问题就转化成了在一个网格图上走路，每次可以选择向上或者向右走 如果可以一步走到边界，则胜利。如图所示 显然边界是必胜态 \(\rm N\) 。一个位置为必胜态 \(\rm N\) ，当且仅当上方或右方至少有一个为 \(\rm P\) ；否则必为 \(\rm P\) 。 如下图所示，其中 \(\color{red}{\large\unicode{x25CB}}\) 为 \(\rm N\) ， \(\color...

Fraktur 哥特体 鉴于最近看到 \(\mathfrak{R}(z)\) 和 \(\mathfrak{I}(z)\) 然后发现自己根本看不懂，于是来补习一下 哥特体或哥德体（英语：Blackletter，德语：Gebrochene Schrift）是约1150年起至17世纪在西欧广泛使用的字体，特点是非常夸张华丽。在德国，哥特体沿用至二战结束。德文尖角体为哥特体的典型字体，在西方有时指代全部哥特体；有时也称为“老英文字体（Old English）”。 如下所示（二、四两行用于对比） \[ \large\begin{array}{c} \mathfrak{A}&\mathfrak{B}&\mathfrak{C}&\mathfrak{D}&\mathfrak{E}&\mathfrak{F}&\mathfrak{G}&\mathfrak{H}&\mathfrak{I}&\mathfrak{J}&\mathfrak{K}&\mathfrak{L}&\mathfrak{M}&...

洛谷P6960 [NEERC2017] Interactive Sort 题解 题目链接：P6960 [NEERC2017] Interactive Sort 题意： 这是一道 IO 交互题。 有一个长度为 \(n~(n\le 10^4)\) 的排列，将排列按奇偶分为两个序列 记所有偶数组成的序列为 \(a\) ，所有奇数组成的序列为 \(b\) ，初始未知。 你可以进行不超过 \(3\times 10^5\) 次询问 ? i j，每次交互库会返回一个 < 或 > 表示 \(a_i\) 和 \(b_j\) 的大小关系。 最后你需要求出 \(a,b\) 并输出，格式为 ! a b。保证数据随机。 首先最简单的方案就是暴力询问每个偶数和每个奇数。 注意到每次询问偶数 \(a_i\) ，都会将奇数序列分为两个集合，分别是大于 \(a_i\) 的和小于 \(a_i\) 的。（\(a_i=n\) 除外） 那么当我们每询问出一个 \(a_i\) ，\(b\) 中的某个集合就会分成两个。 如果我们取集合内的任意一个元素作为集合的权值，那么这些集合的权值显然是单调的 于是对于每个...

《组合数学》 §2.3 学习笔记（下） 传送门：《组合数学》 §2.3 学习笔记（上） 2.3.1 普通生成函数 事实 2.3.20 若 \(f(x) = \sum_{n=0}^{\infty}a_nx^n\) ，则 \(\{a_{n+1}\}_{n=0}^{\infty}\) 的普通生成函数是 \[ \frac{f(x) - a_0}{x} \] 事实 2.3.21 若 \(f(x) = \sum_{n=0}^{\infty}a_nx^n\) ，则 \(\{a_{n+2}\}_{n=0}^{\infty}\) 的普通生成函数是 \[ \frac{f(x) - a_0 - a_1x}{x^2} \] 性质 2.3.22 若 \(f(x) = \sum_{n = 0}^{\infty}a_nx^n\) ，则 \(\{a_{n + k}\}_{n=0}^{\infty}\) 的普通生成函数是 \[ \frac{f(x) - a_0 - a_1x - \cdots - a_{k-1}x^{k-1}}{x^k} \] 事实 2.3.23 若 \(f(x) = \sum_{n = 0}^{...

《组合数学》 §2.3 学习笔记（上） 前言：可以参考 生成函数 学习笔记 定义 2.3.1 数列 \(\{a_n\}_{n=0}^{\infty}\) 的普通生成函数是下面的形式级数 \[ f(x) = \sum_{n=0}^{\infty} a_nx^n \] 定义 2.3.2 数列 \(\{a_n\}_{n=0}^{\infty}\) 的指数型生成函数是下面的形式级数 \[ f(x) = \sum_{n=0}^{\infty}\frac{a_n}{n!}x^n \] 定义 2.3.3 数列 \(\{a_n\}_{n=1}^{\infty}\) 的 Dirichlet 生成函数（狄利克雷生成函数）是下面的形式级数 \[ f(s) = \sum_{n=1}^{\infty} \frac{a_n}{n^s} \] 例 2.3.4 数列 \(\{1\}_{n=0}^{\infty}\) 的普通生成函数是 \[ \sum_{n=0}^{\infty}x^n = \frac{1}{1-x} \] 同时它的指数型生成函数是 \[ \sum_{n=0}^{\infty}\frac{x^n}...

《组合数学》 §2.2 学习笔记 例 2.2.1 （Hanoi 塔问题） 这个东西都快讲烂了，\(h_n = 2^n-1\) 。 一般地，称数列 \(\{h_n\}_{n=0}^{\infty}\) 满足 \(k\) 阶常系数线性非齐次递推关系，若对所有的 \(n \ge k\) 有 \[ h_n = a_1 h_{n-1} + a_2h_{n-2} + \cdots a_kh_{n-k} + f(n) \] 其中 \(a_k \ne 0~(k \ge 1)\) 为常数，\(f(n) \ne 0\) 是关于 \(n\) 的函数。 对于线性非齐次递推关系的通解，可以通过求解其其次部分的通解， 再找到一个满足原递推关系的特解来得到，即 线性非齐次递推关系 \(=\) 线性齐次递推关系的通解 \(+\) 线性非齐次递推关系的一个特解。 其中所谓的“特解”并不唯一，构造方法也不固定。对于一般的 \(f(n)\) ，还不知道寻找它的特解的普遍办法， 一般只能用观察猜想特解的形式再用待定系数法来确定系数。 例如，若 \(f(n)\) 是 \(n\) 的 \(t\) 次多项式，可设特解也是 \...