洛谷P1829 [国家集训队] Crash的数字表格 / JZPTAB 题解
洛谷P1829 [国家集训队] Crash的数字表格 / JZPTAB 题解 题目链接:P1829 [国家集训队] Crash的数字表格 / JZPTAB 题意: 给定 \(n,m\) 求 \[ \sum_{i=1}^n \sum_{j=1}^m \operatorname{lcm}(i, j) \] 模 \(20101009\) 的结果。 数据范围:\(1\le n,m \le 10^7\) 。 来讲一个杜教筛的解法吧。 首先先规定一下 \(n \le m\) ,然后开始推式子 \[ \begin{aligned} \mathrm{Ans} &= \sum_{i=1}^n \sum_{j=1}^m \frac{i \cdot j}{\gcd(i, j)} \\[6pt]&= \sum_{i=1}^n \sum_{j=1}^m \sum_{d|i, d| j}\left[\gcd\left(\frac{i}{d}, \frac{j}{d}\right)=1\right]\cdot \frac{i \cdot j}{d} \\[6pt]&= \sum_{...
洛谷P3768 简单的数学题 题解
洛谷P3768 简单的数学题 题解 题目链接:P3768 简单的数学题 题意: 输入一个整数 \(n\) 和一个整数 \(p\),你需要求出: \[ \left(\sum_{i=1}^n\sum_{j=1}^n ij \gcd(i,j)\right) \bmod p \] 其中 \(\gcd(a,b)\) 表示 \(a\) 与 \(b\) 的最大公约数。 输入格式: 一行两个整数 \(p,n\)。 输出格式: 一行一个整数表示答案。 数据范围: \(1\le n \le 10^{10},~5 \times 10^8 \leq p \leq 1.1 \times 10^9\) 且 \(p\) 为质数。时限 4s。 考虑欧拉反演。 \[ \begin{aligned} \sum_{i=1}^n \sum_{j=1}^n i j \operatorname{gcd}(i, j) & =\sum_{i=1}^n \sum_{j=1}^n i j \sum_{k\mid i,\, k\mid j} \varphi(k) \\[4pt]& =\sum_{k=1}^n \v...
AT_agc024_e [AGC024E] Sequence Growing Hard 题解
AT_agc024_e [AGC024E] Sequence Growing Hard 题解 题目链接:AT_agc024_e [AGC024E] Sequence Growing Hard 题意: 给定 \(n,m,P\) ,问有多少个序列组 \((A_0,A_1,\cdots,A_n)\) 满足: 序列 \(A_i\) 的元素个数为 \(i\) ; 所有元素都在 \([1,m]\) 内; \(\forall i\in[0,n)\) ,\(A_i\) 是 \(A_{i+1}\) 的子序列且 \(A_i\) 的字典序小于 \(A_{i+1}\) 。 输出在\(\bmod P\) 意义下的答案. 数据范围: \(1\le n, m \le 300,~2\le P \le 10^9\) 。 正着考虑看上去很麻烦,不妨反着来看这个序列组。 显然这个序列组就是从 \(A_n\) 删除某个元素得到 \(A_{n-1}\) ,再删除一个得到 \(A_{n-2}\) ,以此类推。 那么根据字典序的性质,如果我们删除 \(i\) 位置的元素,得到一个字典序更小的, 就要求 \(i\) 后...
洛谷P3673 小清新计数题 题解
洛谷P3673 小清新计数题 题解 题目链接:P3673 小清新计数题 题意: 小 A 正在电脑上玩一个叫做 Truth or Lie 的游戏。 游戏开始时电脑会给出 \(n\) 句话,每句话形如「第 \(x\) 句话为真」或「第 \(x\) 句话为假」, 其中 \(x\) 是一个 \(1\) 到 \(n\) 的整数,你只要选择 Good 或者 Bad,Good 表示可以决定每句话的真假使每句话的内容都成立,Bad 反之。 作为一个菜鸡,小 A 只会不停地点 Good,靠脸过关。 在无数次失败后,非洲人小 A 发现游戏每关中,每句话包含的是「真」还是「假」是固定的,但是每句话中的 \(x\) 是在 \(1\) 到 \(n\) 均匀随机的。 现在小 A 告诉了你某一关每句话的真假,用一个 \(01\) 序列表示。第 \(i\) 位为 \(0\) 表示第 \(i\) 句话包含「假」,否则表示包含「真」。现在他想要知道使得点击 Good 正确的方案数。 由于方案数可能比较大,你需要输出方案数对 \(998244353\) 取模的结果。 输入格式 一行一个 \(01\) 序列,它的长度...
洛谷P4213 【模板】杜教筛 题解
洛谷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 * g)...
欧拉反演
欧拉反演 前言:因为一直记错这个东西,所以来写一下。 欧拉反演 \[ \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} \varphi(d) \\[6...
洛谷P8347 「Wdoi-6」另一侧的月 题解
洛谷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] 移动金币 题解 题目链接: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 题解 题目链接: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 题解 题目链接: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\) 堆石子...
AT_agc002_e [AGC002E] Candy Piles 题解
AT_agc002_e [AGC002E] Candy Piles 题解 题目链接:AT_agc002_e [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}}\...
Fraktur 哥特体
Fraktur 哥特体 鉴于最近看到 \(\mathfrak{R}(z)\) 和 \(\mathfrak{I}(z)\) 然后发现自己根本看不懂,于是来补习一下 哥特体或哥德体(英语:Blackletter,德语:Gebrochene Schrift)是约1150年起至17世纪在西欧广泛使用的字体,特点是非常夸张华丽。在德国,哥特体沿用至二战结束。德文尖角体为哥特体的典型字体,在西方有时指代全部哥特体;有时也称为“老英文字体(Old English)”。 如下所示(第二、四两行是正常字体,仅用于对比) \[ \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}&am...
![洛谷P1829 [国家集训队] Crash的数字表格 / JZPTAB 题解](/qwq/img/p195.webp)

![AT_agc024_e [AGC024E] Sequence Growing Hard 题解](/qwq/img/p184.webp)



![洛谷P5363 [SDOI2019] 移动金币 题解](/qwq/img/p182.webp)

![洛谷P3480 [POI2009] KAM-Pebbles 题解](/qwq/img/p113.webp)
![AT_agc002_e [AGC002E] Candy Piles 题解](/qwq/img/p197.webp)



![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p214.webp)
![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p230.webp)