Q779’s Blog

洛谷P5488 差分与前缀和 题解 题目链接：P5488 差分与前缀和 题意： 给定一个长为 \(n\) 的序列 \(a\)，求出其 \(k\) 阶差分或前缀和。 结果的每一项都需要对 \(1004535809\)​ 取模。 输入格式： 第一行三个整数 \(n,k,t\)，若 \(t=0\) 表示求前缀和，\(t=1\) 表示求差分。 第二行 \(n\) 个整数，表示序列 \(a\)​。 输出格式： 输出一行 \(n\) 个整数，表示 \(a\) 的 \(k\) 阶差分或前缀和。 数据范围： \(1 \le n \le 10^5,~0 \le a_i \le 10^9,~1\le k \le 10^{2333}, k \not \equiv 0 \pmod{1004535809}\)​​ \(\mathcal{Part}\ 1\) 设 \(F(x) = \sum_{n \ge 0} a_nx^n\) 是序列 \(a\) 的生成函数。 众所周知，它的前缀和就是 \(F(x)\times G(x)\) ，其中 \(G(x)=\sum_{n\ge 0}x^n\) ，因为 \[ \b...

note[18] 本文是有关命题的一些奇怪小知识。 题：令 \(x \in \mathbb{R}\) ，若 \(x^2 < 0\) ，则 \(x < 0\) 。该命题是否为真命题？ 解：是真命题。 为什么呢？考虑两种解法 考察原命题的逆否命题。对于命题 \(p\to q\) ，其逆否命题为 \(\neg q \to \neg p\) 定理1：任何命题等价于它的逆否命题（逆否命题的真假性与原命题一致）。 在本题中，命题的逆否命题为「令 \(x \in \mathbb{R}\) ，若 \(x > 0\) ，则 \(x^2>0\) 」，显然为真，则原命题为真命题。 命题「假命题 \(\to\)​​ 真/假命题」是真命题（假命题可以推出任何真命题） 这个可以参考定义： 设 \(p,q\) 是命题，复合命题「若 \(p\) 则 \(q\) 」称作 \(p\) 与 \(q\) 的蕴含式，记作 \(p \to q\) 定理2：命题 \(p\to q\) 为假命题当且仅当 \(p\) 为真命题且 \(q\) 为假命题。 推论1：设 \(p,q\) 是命题，则 \(p ...

CF468C Hack it! 题解 题目链接：Hack it! 题意： 小 X 最近遇到了下面的问题。 我们定义函数 \(f(x)\) 为 \(x\) 的各个数位之和。 比如说，\(f(1234)=1+2+3+4=10\)。任务是，计算 \(\sum_{i=l}^rf(i)\bmod a\)​ 的值。 小 X 很快就解决了这个问题。于是小 X 锁定了这道题，然后开始 hack 别人。他看到了下面这段代码： ans = solve(l, r) % a; if (ans <= 0) ans += a; 显而易见地，这段代码会在 \(\sum_{i=l}^rf(i)\equiv 0 \pmod a\) 时输出错误。 小 X 会告诉你题目中的 \(a\)​ 是多少，现在请你为小 X 构造一个 hack 数据。 输入格式： 输入包括一行，即小 X 给定的 \(a\) 的值（\(1\le a\le 10^{18}\)）。输入保证有解。 输出格式： 输出两个整数：\(L,R\)，满足 \(1\leq L\leq R\leq 10^{200}\)，同时 \(\sum_{i=l}^rf(...

洛谷P2414 [NOI2011] 阿狸的打字机 题解 题目链接：P2414 [NOI2011] 阿狸的打字机 题意： 阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有 \(28\) 个按键，分别印有 \(26\) 个小写英文字母和 B、P 两个字母。经阿狸研究发现，这个打字机是这样工作的： 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。 按一下印有 B 的按键，打字机凹槽中最后一个字母会消失。 按一下印有 P 的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。 例如，阿狸输入 aPaPBbP，纸上被打印的字符如下： a aa ab 我们把纸上打印出来的字符串从 \(1\) 开始顺序编号，一直到 \(n\)。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数 \((x,y)\)（其中 \(1\leq x,y\leq n\)），打字机会显示第 \(x\) 个打印的字符串在第 \(y\) 个打印的字符串中出现了多少次。 阿狸发现了这个功能以后很兴奋，他想写个程序完成...

洛谷P2602 [ZJOI2010] 数字计数 题解 & 数位dp 模板 题目链接：P2602 [ZJOI2010] 数字计数 题意： 给定两个正整数 \(l\) 和 \(r\)，求在 \([l,r]\) 中的所有整数中，每个数码(digit)各出现了多少次。 输入格式： 仅包含一行两个整数 \(l,r\)，含义如上所述。 输出格式： 包含一行十个整数，分别表示 \(0\sim 9\) 在 \([l,r]\) 中出现了多少次。 数据范围： 保证 \(1\le l\le r\le 10^{12}\)。 本题是 数位dp 的模板题（鉴于本人竟然没有数位dp的板子） 设 \(f(i,j)\) 表示（从低到高）考虑到第 \(i\) 位，当前枚举的数码 \(d\) 出现了 \(j\)​ 次时的方案数 这样设计的好处在于边界是 \(f(0,j)=j\) ，可以很方便的得到答案，而且状态数很少，只有 \(12 \times 12\) 。 数位dp一般使用记忆化搜索，复杂度一般等于 \(\mathcal{O}\left(\texttt{状态数}\right)\)​ 乘上一个小常数（没...

洛谷P3560 [POI2013] LAN-Colorful Chain 题解 题目链接：P3560 [POI2013] LAN-Colorful Chain 题意： 小 Bajtuś 非常喜欢玩彩色链条。他已经收集了相当多的链条，不过有些他喜欢的比其他的更多。每条链条由若干个彩色链环组成。Bajtazar 注意到 Bajtuś 对美学有非常精确的偏好。具体来说，Bajtuś 认为一段连续的链条是漂亮的，如果它恰好包含 \(l_1\) 个颜色为 \(c_1\) 的链环，\(l_2\) 个颜色为 \(c_2\) 的链环，……，\(l_m\) 个颜色为 \(c_m\) 的链环，并且不包含任何其他颜色的链环。 链条的吸引力等于漂亮的（连续）片段的数量。Bajtazar 通过试错法找出了 \(l_1, \cdots , l_m\) 和 \(c_1, \cdots , c_m\) 的值。 现在他想买一条新的链条，并请求你编写一个程序来帮助他购买。 省流：对于字符串 \(a\) ，找到漂亮的子串的总数。 输入格式： 标准输入的第一行包含两个整数 \(n\) 和 \(m\) （ \(1 \l...

洛谷P8819 [CSP-S 2022] 星战 题解 题目链接：P8819 [CSP-S 2022] 星战 题意： 在这一轮的星际战争中，我方在宇宙中建立了 \(n\) 个据点，以 \(m\) 个单向虫洞连接。我们把终点为据点 \(u\) 的所有虫洞归为据点 \(u\) 的虫洞。 战火纷飞之中这些虫洞很难长久存在，敌人的打击随时可能到来。这些打击中的有效打击可以分为两类： 敌人会摧毁某个虫洞，这会使它连接的两个据点无法再通过这个虫洞直接到达，但这样的打击无法摧毁它连接的两个据点。 敌人会摧毁某个据点，由于虫洞的主要技术集中在出口处，这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁。 注意：摧毁只会导致虫洞不可用，而不会消除它的存在。 为了抗击敌人并维护各部队和各据点之间的联系，我方发展出了两种特种部队负责修复虫洞： A 型特种部队则可以将某个特定的虫洞修复。 B 型特种部队可以将某据点的所有损坏的虫洞修复。 考虑到敌人打击的特点，我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复，处于可用状态，那么这个据点也是可用的。...

洛谷P4727 [HNOI2009] 图的同构计数 题解 题目链接：P4727 [HNOI2009] 图的同构计数 题意： 小雪在了解到以上情况后，自认为直接挑战终极难题还有不少困难，于是决定先从简单的问题做起，具体来说，他对图同构问题产生了浓厚的兴趣。\(A\)图与\(B\)图被认为是同构的是指：\(A\)图的顶点经过一定的重新标号以后，\(A\)图的顶点集和边集要完全与\(B\) 图一一对应。 小雪现在专注于如何判断两个图是否同构，同时他还想知道两两互不同构的含\(N\)个点的图有多少种。众所周知含\(N\)个点的简单图最多有 \(\frac{N(N-1)}{2}\) 条边，这样含\(N\)个点的图有 \(2^{\frac{N(N-1)}{2}}\) 种可能的情况。显然这些图中有很多图是同构的，小雪想知道的便是：若同构的图算成一种，则有多少种不同的图。他把这个任务丢给了你，在他想出来之前快点解决吧！ 输入格式： 从文件input.txt中读入数据，文件中只有一个非负整数\(N\)，表示图的顶点数。 输出格式： 输出文件output.txt中仅包含一个整数，表示含\(N\)个...

洛谷P4128 [SHOI2006] 有色图 题解 题目链接：P4128 [SHOI2006] 有色图 题意： 如果一张无向完全图（完全图就是任意两个不同的顶点之间有且仅有一条边相连）的每条边都被染成了一种颜色，我们就称这种图为有色图。如果两张有色图有相同数量的顶点，而且经过某种顶点编号的重排，能够使得两张图对应的边的颜色是一样的，我们就称这两张有色图是同构的。以下两张图就是同构的，因为假如你把第一张图的顶点 \((1,2,3,4)\) 置换成第二张图的 \((4,3,2,1)\)，就会发现它们是一样的。 你的任务是，对于计算所有顶点数为 \(n\)，颜色种类不超过 \(m\) 的图，最多有几张是两两不同构的图。由于最后的答案会很大，你只要输出结论模 \(p\) 的余数就可以了（\(p\) 是一个质数）。 输入格式： 输入文件只有一行，由三个正整数 \(n,m,p\) 组成。 输出格式： 即总数模 \(p\) 后的余数。 数据范围： \(1\leq n\leq 53\)，\(1\leq m\leq 1000\)，\(n<p\leq 10^9\)。 本题读完就能看出来是...

洛谷P3353 在你窗外闪耀的星星 题解 题目链接：P3353 在你窗外闪耀的星星 题意： 天空可以理解为一条数轴，在这条数轴上分布着许多颗星星，对于每颗星星都有它的位置 \(X_i\) 和自身的亮度 \(B_i\)。一个位置可能有多颗星星。而窗户所能看到的范围是一个给出的参数 \(W\)​，我们看到的星星也包括窗户边缘的星星。现在，要你求出调整窗户位置后能看到星星的亮度之和最大值。 输入格式： 一行 \(N,W\)，分别代表星星的数量和窗户的宽度。 余下 \(N\) 行，输入 \(X_i\) 和 \(B_i\)，代表星星的坐标和亮度。 输出格式： 一个数字，代表能看到星星的最大亮度和。 数据范围： 对于 \(100\%\) 的数据，\(1 \leq N\leq 10 ^ 5\)，\(0 \leq W\leq 10 ^ 5\)，\(1 \leq X_i\leq 10 ^ 5\)，\(1\leq B_i\leq 100\)。 除 \(W=0\) 的情况外，\(W\) 均为 \(\geq 3\) 的奇数。 把所有的点按 \(x\) 排序，然后维护一个指针 \(p\) 跟着 \(...

CF1608D Dominoes 题解 题目链接：Dominoes 题意： 有 \(n(1 \le n \le 10^5)\) 个多米诺骨牌，每个骨牌由左右两个方格组成。有的方格已经被涂上了白色（W）或者黑色（B），剩下的方格（?）还没有被涂色。你需要给所有未涂色的方格涂上黑色或者白色。 一种涂色方案被认为是合法的，当且仅当存在一种排列骨牌方案使得任意一块牌的右面不同于下一块的左面。特殊地，最后一个骨牌的下一块是第一个骨牌。值得注意的是不能旋转它们，也就是不能交换左右方格的颜色。 两种涂色方案被认为是不同的，当且仅当存在一个方格在一个方案中被涂白在另一个方案中被涂黑。形如 BW WB 和 WB BW 的两个方案被认为是不同的方案。（同时他们都是非法的）。 求方案数对 \(998244353\)​ 取模的结果。 输入：\(n\)​ 行字符串。输出：答案 搬一张图 一般情况： 至少「一个 \(\mathtt{BB}\) 和一个 \(\mathtt{WW}\) 」，剩下的保证「 \(\mathtt{W}\) 个数等于 \(\mathtt{B}\)​​ 个数」即可。 设有 \(a...

CF1540B Tree Array 题解 题目链接：Tree Array 题意： 给定一棵 \(n\)​ 个节点的树。 对于这棵树，我们通过下列方法来生成一个序列： 等概率选择这 \(n\) 个节点中的一个节点，并对这个节点打上标记（初始时没有节点被打上标记） 在所有没被打上标记且与至少一个打上标记的节点相连的节点中等概率选择一个节点并对这个节点打上标记 重复步骤 2 直到所有节点都被打上标记，此时生成的序列就是所有节点编号按照节点被打上标记的时间排序后的形成的序列。 求生成序列的期望逆序对数对 \(10^9+7\)​​ 取模后的值。 输入：树；输出：答案 数据范围： \(2\leq n\leq200\) ，保证给出的是棵树 首先可以发现，这个标记的过程和第一个点息息相关 考虑枚举第一个被标记的点，然后把它提成根节点。 那么现在所有的点对 是祖先关系的，一定会产生贡献 \(0/1\) 的贡献。 不是祖先关系的，当他们的 LCA 被加入后，接下来的任何标记都可以解释为： 两个栈， \(p\) 概率弹第一个栈栈顶，\(p\) 概率弹第二个栈栈顶，\(1-2p\)​ 概率啥...