Q779’s Blog

洛谷P1960 郁闷的记者 题解 题目链接：P1960 郁闷的记者 题意： 你是一个体育报社的记者，你接受到一个艰难的任务：有N支足球队参加足球比赛，现在给你一些比赛的结果，需要你给出各支球队的排名，从1到N。 以下是给你的一些信息： (1)没有平局； (2)不同的球队排名不能相同； (3)对于所有满足l≤a<b≤n，第a名的球队一定可以打败第b名的球队。 给你部分比赛结果，要求给出排名，并且判断是否存在另一种排名方法满足给你的比赛结果。 输入格式 第一行输入N(1≤N≤5000)，表示球队的数量，编号为l到N。第二行输入M(1≤M≤100,000)，表示给出的比赛场数。接下来M行，每行两个整数X_i，Y_i，表示X_i能打败Y_i。 输出格式： 输出包含N+1行，前N行描述球队的排名，第i个数表示第i名的球队，第N+1行包含一个整数，如果为0表示不存在其他的排名方法，如果为1表示还有其他的排名方法。 数据范围： \(1\le N\le 5000,~1\le M\le 10^5\) 。 注意到如果某一时刻出现多个度数为 \(0\) 的结点，则拓扑序不唯一。 时间复杂度 ...

洛谷P2767 树的数量 题解 题目链接：P2767 树的数量 题意： 求出包含 \(n\) 个节点（无标号）的有根 \(m\) 叉树的个数，对 \(10\,007\) 取模。 两个有根树相同，当且仅当其根节点相同，且从左到右每一棵子树也相同。特别地，两个有根树均为空树，视为两个有根树相同。 输入格式： 输入两个整数 \(n\)，\(m\)。 输出格式： 输出包含 \(n\) 个节点（无标号）的有根 \(m\) 叉树的个数，对 \(10\,007\) 取模后的值。数据范围： \(n,m \leq 127\) 这题可以 \(\mathcal{O}(p + \log_m n)\) 做，需要用到生成函数&拉格朗日反演。不会，可以看这篇。 这里讲 dp 的做法。 设 \(f_{i,j}\) 表示 \(i\) 个点，根节点有至多 \(j\) 棵子树时的方案数。考虑转移 枚举点数 \(k\) ，把这 \(k\) 个点拆成一个新的子树算。容易发现不会算重。 \[ f_{i,j} = \sum_{k=0}^{i-1}f_{k,m}\times f_{i-k,j-1} \] 时间复杂度...

\(n\) 倍角公式 居然还写过这玩意 \[ \begin{aligned} \sin n\vartheta &= \sum\limits_{i=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(-1)^iC_n^{2i+1}\cos^{n-2i-1}\vartheta\sin^{2i+1}\vartheta \\[6pt] \cos n\vartheta &= \sum\limits_{i=0}^{\left\lfloor\frac{n}{2}\right\rfloor}(-1)^iC_n^{2i}\cos^{n-2i}\vartheta\sin^{2i}\vartheta \end{aligned} \]

全概率公式&贝叶斯公式 全概率公式 设 \(B_1,B_2 ,\dots B_n\) 为一组两两互斥的事件，且有 \[ \bigcup\limits_{1 \le i \le n} B_i = \Omega \] 则对任意的事件 \(A \in \Omega\) 有 \[ P(A) = \sum_{i=1}^n P(B_i)P(A \mid B_i) \] 贝叶斯公式 设 \(B_1,B_2 ,\dots B_n\) 为一组两两互斥的事件，且有 \[ \bigcup\limits_{1 \le i \le n} B_i = \Omega \] 则对任意的事件 \(A \subseteq \Omega,~A \ne \varnothing\) 有 \[ P(B_i \mid A) = \dfrac{P(B_i)P(A\mid B_i)}{P(A)} = \dfrac{P(B_i)P(A\mid B_i)}{\sum_{i=1}^n P(B_i)P(A \mid B_i)} \]

直线方程 直线方程的几种形式 名称 已知条件 标准方程 适用范围 点斜式 斜率 \(k\) ，直线上一点 \((x_0,y_0)\) \(y-y_0 = k(x-x_0)\) 斜率 \(k\) 存在 斜截式 斜率 \(k\) ，\(y\) 轴上截距 \(b\) \(y=kx+b\) 斜率 \(k\) 存在 两点式 直线上两个定点 \((x_1,y_1),(x_2,y_2)(x_1\ne x_2,y_1\ne y_2)\) \(\dfrac{y-y_1}{y_2-y_1} = \dfrac{x-x_1}{x_2-x_1}\) 不垂直于坐标轴 截距式 \(x,y\) 轴上的截距 \(a,b(ab\ne 0)\) \(\dfrac{x}{a}+\dfrac{y}{b} =1\) 不垂直于坐标轴且不过原点 一般式 \(A,B\) 不同时等于 \(0\) \(Ax+By+C=0\) 通用 点 \((x_0,y_0)\) 到直线 \(Ax+By+C=0\) 的距离公式 \[ d=\dfrac{\left|Ax_0+By_0+C\right|...

线性回归 学习笔记 又是不知道什么时候的，先放在这，待研究。 经验回归直线 \(\bar{y} = \hat{a}\bar{x}+\hat{b}\) ，满足 \[ \begin{cases} \hat{b} = \dfrac{\sum\limits_{i=1}^{n}(x_i-\bar{x})(y_i-\bar{y})}{\sum\limits_{i=1}^{n}(x_i-\bar{x})^2} = \dfrac{\sum\limits_{i=1}^{n}x_iy_i-n\bar{x}\bar{y}}{\sum\limits_{i=1}^{n}x^2-n\bar{x}^2}, \\[8pt] \hat{a} = \bar{y} - \hat{b}\bar{x} \end{cases} \]

辅助角公式及其证明 不知道什么时候写的，属于未发布状态，嗨害嘿。 辅助角公式： \[ a\sin x+b\cos x = \sqrt{a^2+b^2} \sin\left(\textstyle x + \arctan \frac{b}{a}\right) \] 证明： 设 \(-\frac{\pi}{2}<\vartheta<\frac{\pi}{2}\) ，使得 \[ \cos \vartheta =\dfrac{a}{\sqrt{a^2+b^2}} \\ \sin \vartheta = \dfrac{b}{\sqrt{a^2+b^2}} \] 则 \(\vartheta = \arctan \frac{b}{a}\) ，故 \[ \begin{aligned} a\sin x + b\cos x &= \sqrt{a^2+b^2}(\cos \vartheta \sin x + \sin \vartheta \cos x) \\[6pt]&= \sqrt{a^2+b^2} \sin(x + \vartheta) \\[6pt]&= \s...

CF1401D Maximum Distributed Tree 题解 题目链接：CF1401D Maximum Distributed Tree 题意： 给定一棵 \(n\) 个节点，\(n-1\) 条边的树。你可以在每一条树上的边标上边权，使得： 每个边权都为 正整数； 这 \(n-1\) 个边权的 乘积 等于 \(k\)； 边权为 \(1\) 的边的数量最少。 定义 \(f(u,v)\) 表示节点 \(u\) 到节点 \(v\) 的简单路径经过的边权总和。你的任务是让 \(\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} f(i,j)\) 最大。 最终答案可能很大，对 \(10^9+7\) 取模即可。 \(k\) 有可能很大，输入数据中包含了 \(m\) 个质数 \(p_i\)，那么 \(k\) 为这些质数的乘积。 输入格式： 第一行，一个整数 \(t\) \((1\leq t\leq 100)\)，表示多组测试数据个数。对于每一个测试数据： 第一行，一个整数 \(n\) \((2\leq n\leq 10^5)\)，表示树...

【化学】必修一笔记 全部的笔记。虽然化学不咋滴，但是笔记还是记的不少。 估计不会有必修二的笔记和之后的，因为全记在了纸质文稿上。 本 pdf 经过 \(n\) 次修改，修了很多bug，花了很多思维导图，请放心食用（确信 2022-11-06-11-46-51.pdf

【生物】必修一 微量元素&物质检验&科学家事迹 表格 三个表格，人体对部分常见无机盐的需求分析 、 物质的检测或鉴定 和 生物必修一科学家&事迹整理。 2022-11-06-11-29-45.pdf 2022-11-06-11-39-08.pdf

【生物】含 \(n\) 对同源染色体的细胞 产生的配子数 以前写的，应该是必修二的。 假设某雄性动物体细胞含有 \(n\) 对同源染色体 不考虑同源染色体之间发生的片段交换，则该雄性个体的某个精原细胞可产生 \(2\) 种精子。 考虑其中一对或多对同源染色体互换了特定片段，则该雄性个体的某个精原细胞可产生 \(4\) 种精子。 原因：显然，且 \(4\) 个细胞再多也只有 \(4\) 种。 不考虑同源染色体之间发生的片段交换，则该雄性个体可产生 \(2^n\) 种精子。 原因：考虑精原细胞 减数分裂I后期 非同源染色体的自由组合， 则一个次级精母细胞的染色体至多有 \(2^n\) 种，由于不考虑同源染色体之间发生的片段交换， 则每个次级精母细胞只产生 \(2\) 个相同的精细胞（后变形为精子），故共有 \(2^n\) 种。 若 结论3 考虑同源染色体间发生的片段交换，则没有意义了（要么概率极小要么种类特别多）

【生物】细胞器结构功能整理 早期总结文章，然后发现这玩意不太好上传博客 于是新建了一个文件夹专门放这些玩意（雾 2022-11-06-11-14-17.pdf 那些参考的图片大多来自中文维基。