洛谷P5072 [Ynoi2015] 盼君勿忘 题解
洛谷P5072 [Ynoi2015] 盼君勿忘 题解 在太阳西斜的这个世界里,置身天上之森。等这场战争结束之后,不归之人与望眼欲穿的众人, 人人本着正义之名,长存不灭的过去、逐渐消逝的未来。我回来了,纵使日薄西山,即便看不到未来,此时此刻的光辉,盼君勿忘。————世界上最幸福的女孩 题目链接:P5072 [Ynoi2015] 盼君勿忘 题意: 珂朵莉给了你一个序列,每次查询一个区间 \([l,r]\) 中所有子序列分别去重后的和 \(\bmod\ p\)。 输入格式: 第一行两个整数 \(n,m\)。 第二行 \(n\) 个整数表示这个序列。 之后 \(m\) 行,每行三个整数 \(l,r,p\) 表示查询的区间与模数。 输出格式: \(m\) 行,每行输出一个整数表示答案。 数据范围: \(1\leq n,m,a_i \leq 10^5\),\(1\leq p\leq 10^9\),\(1\leq l\leq r\leq n\)。 可以发现,如果一个数 \(a_i\) 在区间中出现了 \(k\) 次,则它的贡献为 \[ a_i \times \left(2^{r-l+1}-...
等式两侧求导是否正确?
等式两侧求导是否正确? 答案:一般不正确。只有等式是恒等式时正确。 经典反例:求解 \(x^2=x\) 。如果你两边同时求导,会得到 \(2x=1\) 即 \(x=\frac{1}{2}\) ,纯属胡扯。 那么为什么不能同时求导呢? 因为上述反例中我们是在求方程的解,即对于 \(x=\) 某些值时,等式才成立 而导数是考察函数在某一区间上斜率的变化状况,这俩没什么直接关系。 好消息是,等式两侧求导在一些情况下是可以的,这种情况叫作:恒等式。 举例:设 \(f(x)\) 是可导函数,求证若 \(f(x)\) 是偶函数,\(f^{\prime}(x)\) 是奇函数。 证明: 由偶函数性质得 \[ f(x) - f(-x) = 0 \] 两侧求导 \[ f^{\prime}(x)+ f^{\prime}(-x) = 0 \] 显然 \(f^{\prime}(x)\) 是奇函数。\(\square\) 提示:这里为什么可以求导呢?因为对于偶函数 \(f(x)\) ,\(f(x)-f(-x)=0\) 是一个恒等式
洛谷P5488 差分与前缀和 题解
洛谷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]
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! 题解
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] 阿狸的打字机 题解 题目链接: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] 数字计数 题解 & 数位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一般使用记忆化搜索,复杂度一般等于 \(O\left(\texttt{状态数}\right)\) 乘上一个小常数(没人会卡这个常数的),当然是...
洛谷P3560 [POI2013] LAN-Colorful Chain 题解
洛谷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] 星战 题解 题目链接:P8819 [CSP-S 2022] 星战 题意: 在这一轮的星际战争中,我方在宇宙中建立了 \(n\) 个据点,以 \(m\) 个单向虫洞连接。我们把终点为据点 \(u\) 的所有虫洞归为据点 \(u\) 的虫洞。 战火纷飞之中这些虫洞很难长久存在,敌人的打击随时可能到来。这些打击中的有效打击可以分为两类: 敌人会摧毁某个虫洞,这会使它连接的两个据点无法再通过这个虫洞直接到达,但这样的打击无法摧毁它连接的两个据点。 敌人会摧毁某个据点,由于虫洞的主要技术集中在出口处,这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁。 注意:摧毁只会导致虫洞不可用,而不会消除它的存在。 为了抗击敌人并维护各部队和各据点之间的联系,我方发展出了两种特种部队负责修复虫洞: A 型特种部队则可以将某个特定的虫洞修复。 B 型特种部队可以将某据点的所有损坏的虫洞修复。 考虑到敌人打击的特点,我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复,处于可用状态,那么这个据点也是可用的。...
洛谷P4727 [HNOI2009] 图的同构计数 题解
洛谷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] 有色图 题解 题目链接: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 在你窗外闪耀的星星 题解 题目链接: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\) 跟着 \(...
![洛谷P5072 [Ynoi2015] 盼君勿忘 题解](/qwq/img/p212.webp)


![note[18]](/qwq/img/p80.webp)

![洛谷P2414 [NOI2011] 阿狸的打字机 题解](/qwq/img/p98.webp)
![洛谷P2602 [ZJOI2010] 数字计数 题解 & 数位dp模板](/qwq/img/p208.webp)
![洛谷P3560 [POI2013] LAN-Colorful Chain 题解](/qwq/img/p168.webp)
![洛谷P8819 [CSP-S 2022] 星战 题解](/qwq/img/p184.webp)
![洛谷P4727 [HNOI2009] 图的同构计数 题解](/qwq/img/p164.webp)
![洛谷P4128 [SHOI2006] 有色图 题解](/qwq/img/p113.webp)



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