Q779’s Blog

洛谷P2303 [SDOI2012] Longge 的问题 题解 题目链接：P2303 [SDOI2012] Longge 的问题 题意： 给定一个整数 \(n\)，你需要求出 \(\sum\limits_{i=1}^n \gcd(i, n)\) 。 输入格式： 输入只有一行一个整数，表示 \(n\)。 输出格式： 输出一行一个整数表示答案。 数据范围： \(1\leq n< 2^{32}\)。 根据数学题套路，我们枚举 \(\gcd(i,n)\) 的值。 \[ \begin{aligned} \sum_{i=1}^n \gcd(i, n) &=\sum_{d \mid n} d \sum_{i=1}^n[\gcd(i, n)=d] \\[6pt]&=\sum_{d \mid n} d \sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\left[\gcd\left(i, \frac{n}{d}\right)=1\right] \\[6pt]&=\sum_{d \mid n} d\cdot \var...

范德蒙德卷积公式 (Vandermonde’s Identity) 美观起见，证明在 Part 2 。 Part 1 范德蒙德卷积公式： \[ \sum_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i} = \dbinom{n+m}{k} \] 推论1： \[ \sum_{i=-r}^s\dbinom{n}{r+i}\dbinom{m}{s-i}=\dbinom{n+m}{r+s} \] 推论2： \[ \sum_{i=1}^n\dbinom{n}{i}\dbinom{n}{i-1}=\dbinom{2n}{n-1} \] 推论3： \[ \sum_{i=0}^{n}\dbinom{n}{i}^2 = \dbinom{2n}{n} \] 推论4： \[ \sum_{i=0}^{m}\dbinom{n}{i}\dbinom{m}{i} = \dbinom{n+m}{m} \] Part 2 范德蒙德卷积公式 证明： \[ \begin{aligned} \sum_{k=0}^{n+m}\dbinom{n+m}{k}x^k &=(x+1)^{n+m}...

洛谷P8817 [CSP-S 2022] 假期计划 题解 题目链接：P8817 [CSP-S 2022] 假期计划 题意： 小熊的地图上有 \(n\) 个点，其中编号为 \(1\) 的是它的家、编号为 \(2, 3, \ldots, n\) 的都是景点。部分点对之间有双向直达的公交线路。如果点 \(x\) 与 \(z_1\)、\(z_1\) 与 \(z_2\)、……、\(z_{k - 1}\) 与 \(z_k\)、\(z_k\) 与 \(y\) 之间均有直达的线路，那么我们称 \(x\) 与 \(y\) 之间的行程可转车 \(k\) 次通达；特别地，如果点 \(x\) 与 \(y\) 之间有直达的线路，则称可转车 \(0\) 次通达。 很快就要放假了，小熊计划从家出发去 \(4\) 个不同的景点游玩，完成 \(5\) 段行程后回家：家 \(\to\) 景点 A \(\to\) 景点 B \(\to\) 景点 C \(\to\) 景点 D \(\to\) 家且每段行程最多转车 \(k\) 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景...

ubuntu 合上笔记本盖子不休眠的方法 我的ubuntu，她又复活哩！ 现在基本上是用 VNC Sever 本地远程操纵了，也不知道有啥用 打开终端，输入 sudo nano /etc/systemd/logind.conf 你会看到一大堆的注释，找到 #HandleLidSwitch=suspend 把它改成（别忘了删掉 # 啊） HandleLidSwitch=ignore 然后重启一下就好了。

【物理】闭合电路的欧姆定律 属于高中物理必修三的内容。要不是会考有实验操作考试我怎么会现在补这个 一、电动势 定义：在电源内部，非静电力把正电荷从负极移动到正极所做的功，与被移动的电荷的电荷量的比值叫做电源的电动势。 公式： \(E = \frac{W}{q}\) （单位：伏特 \(V\) ） 物理意义： 反映电源把其他形式的能转化为电能的本领大小 在数值上等于非静电力把 \(1\ \mathrm{C}\) 的正电荷在电源内部从负极移送到正极所做的功 二、闭合电路的欧姆定律 1. 闭合电路组成 用导线把电源、用电器连成的闭合电路，可以分为外电路和内电路。 外电路：电源以外的电路叫作外电路。 在外电路中，电流由高电势处流向低电势处，沿电流方向电势降低。 内电路：电源内部叫作内电路。 在内电路中，非静电力做功使正电荷由负极移到正极，故电流由电源负极流向电源正极。 因为电源有内阻 \(r\) ，所以沿电流方向电势也降低。 2. 闭合电路的能量转化 外电路：正电荷在恒定电场作用下由正极移向负极。 内电路：非静电力做功，提供全电路消耗的电能。 纯电阻电路有 \[ W = Q_{...

洛谷P3959 [NOIP2017 提高组] 宝藏 题解 题目链接：P3959 [NOIP2017 提高组] 宝藏 题意： 参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 \(n\) 个深埋在地下的宝藏屋， 也给出了这 \(n\) 个宝藏屋之间可供开发的 \(m\) 条道路和它们的长度。 小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。 小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。 在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。 新开发一条道路的代价是 \(\mathrm{L} \times \mathrm{K}\)。其中 \(\mathrm{L}\) 代表这条道路的长度，\(\math...

CF1202E You Are Given Some Strings… 题解 题目链接：CF1202E You Are Given Some Strings… 题意： 给定文本串 \(t\) 和 \(n\) 个模式串 \(s_i\) ，求 \[ \sum_{i=1}^n\sum_{j=1}^nf(s_i + s_j) \] \(f(s)\) 定义为 \(s\) 在 \(t\) 中出现的次数，\(s_i+s_j\) 定义为拼接字符串 \(s_i\) 和 \(s_j\) 。 输入格式： 一行 \(t\) ，一行 \(n\) ，接下来 \(n\) 行 \(s_i\) 。 输出格式： 一行，答案。 数据范围： \(1\le |t|,\sum |s_i| \le 2\times 10^5\) 。 这种题肯定是考虑某个串的贡献啦。 这里我们考虑枚举划分点 \(x\) 。记该点前为 \(s_i\) ，该点后为 \(s_j\) 统计出每个 \(x\) 的 \(f(x),g(x+1)\) 分别表示前后的个数。 怎么统计呢？注意到 \(f(x)\) 其实就是 \(t_{1 \cdots x}\)...

洛谷P5829 【模板】失配树 题解 题目链接：P5829 【模板】失配树 题意： 给定一个字符串 \(s\)，定义它的 \(k\) 前缀 \(\mathsf{pre}_k\) 为字符串 \(s_{1\dots k}\)，\(k\) 后缀 \(\mathsf{suf}_k\) 为字符串 \(s_{|s|-k+1\dots |s|}\)，其中 \(1 \le k \le |s|\)。 定义 \(\mathrm{Border}(s)\) 为对于 \(i \in [1, |s|)\)，满足 \(\mathsf{pre}_i = \mathsf{suf}_i\) 的字符串 \(\mathsf{pre}_i\) 的集合。\(\mathrm{Border}(s)\) 中的每个元素都称之为字符串 \(s\) 的 \(\operatorname{border}\)。 有 \(m\) 组询问，每组询问给定 \(p,q\)，求 \(s\) 的 \(\boldsymbol{p}\) 前缀 和 \(\boldsymbol{q}\) 前缀 的 最长公共 \(\operatorname{border}\)...

洛谷P4316 绿豆蛙的归宿 题解 题目链接：P4316 绿豆蛙的归宿 题意： 给出张 \(n\) 个点 \(m\) 条边的有向无环图，起点为 \(1\)，终点为 \(n\)，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。 绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 \(k\) 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 \(\frac{1}{k}\) 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？ 输入格式： 输入的第一行是两个整数，分别代表图的点数 \(n\) 和边数 \(m\)。 第 \(2\) 到第 \((m + 1)\) 行，每行有三个整数 \(u, v, w\)，代表存在一条从 \(u\) 指向 \(v\) 长度为 \(w\) 的有向边。 输出格式： 输出一行一个实数代表答案，四舍五入保留两位小数。 数据范围： 保证 \(1 \leq n \leq 10^5,~1 \leq m \leq 2 \times n,~1 \leq u, v \leq n,~1 \leq w \le...

洛谷P4550 收集邮票 题解 题目链接：P4550 收集邮票 题意： 有 \(n\) 种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是 \(n\) 种邮票中的哪一种是等概率的，概率均为 \(1/n\)。但是由于凡凡也很喜欢邮票，所以皮皮购买第 \(k\) 次邮票需要支付 \(k\) 元钱。 现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。 输入格式： 一行，一个数字 \(N\)（\(N \le 10000\)）。 输出格式： 输出要付出多少钱，保留二位小数。 直接求花费比较麻烦，因为不知道确切次数什么的。 俗话说，概率要顺推，期望要逆推。 考虑设 \(f_i\) 表示取了 \(i\) 种邮票，取完剩下的期望次数。显然 \(f_n = 0\) 。 \[ f_i = \frac{i}{n}\times f_i + \frac{n-i}{n} \times f_{i+1} + 1 \] 解下方程就是 \[ f_i = f_{i+1} + \frac{n}{n-i} \] 设 \(g_i\...

洛谷P1850 [NOIP2016 提高组] 换教室 题解 题目链接：P1850 [NOIP2016 提高组] 换教室 题意： 对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。 在可以选择的课程中，有 \(2n\) 节课程安排在 \(n\) 个时间段上。在第 \(i\)（\(1 \leq i \leq n\)）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 \(c_i\) 上课，而另一节课程在教室 \(d_i\) 进行。 在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 \(n\) 节安排好的课程。如果学生想更换第 \(i\) 节课程的教室，则需要提出申请。若申请通过，学生就可以在第 \(i\) 个时间段去教室 \(d_i\) 上课，否则仍然在教室 \(c_i\) 上课。 由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 \(i\) 节课程的教室时，申请被通过的概率是一个已知的实数 \(k_i\)，并且对于不同课程的申请，被通过的概率是互相独立的。 学校规定，所有的申请只能在学...

洛谷P1654 OSU! 题解 题目链接：P1654 OSU! 题意： osu 是一款群众喜闻乐见的休闲软件。 我们可以把osu的规则简化与改编成以下的样子: 一共有 \(n\) 次操作，每次操作只有成功与失败之分，成功对应 \(1\) ，失败对应 \(0\) ，\(n\) 次操作对应为 \(1\) 个长度为 \(n\) 的 01 串。在这个串中连续的 \(X\) 个 \(1\) 可以贡献 \(X^3\) 的分数，这 \(X\) 个 \(1\) 不能被其他连续的 \(1\) 所包含（也就是极长的一串 \(1\) ，具体见样例解释） 现在给出 \(n\) ，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留 \(1\) 位小数。 输入格式： 第一行有一个正整数 \(n\) ，表示操作个数。接下去 \(n\) 行每行有一个 \([0,1]\) 之间的实数，表示每个操作的成功率。 输出格式： 只有一个实数，表示答案。答案四舍五入后保留 \(1\) 位小数。 数据范围： \(1 \le n \le 10^5\) 显然期望dp。但是这个贡献不太好计算。 因为它是一个整体去算的，...