寒假作业

何意味

上榜了,hyw 今天没事干又去看了看“ACGO马上AK赛”,em...难评 依旧是最强的人出最一般的题 总共8888罐头，那万一人太多了不就只能拿到几个罐头了吗？？？

关于团队角色设置的想法

结论 在角色管理-新增角色中为新增角色自定义权限 理由 不得不说 ACGO官方 对团队的个性化还是很友好的，但是我对于角色管理这方面还有一个好想法 既然可以在角色管理中设置一个新的自定义角色，那就代表这个自定义角色有一个在团队中的特色 但现在看来，里面的设置权限中并没有显示类似自定义的内容，所以我就发布了今天这篇帖子 一旦增加这种自定义权限，团队的玩法将更加有趣 比如说，我们把《三角洲行动》中的一个角色[安全总监]德穆兰加进来，在自定义权限中就可以给德穆兰设置维护团队的相关权限 感谢大家阅读这篇文章，春节也快到了，预祝大家新年快乐！

互动｜「寒假生存实录」开播中！

🌟「寒假生存实录」开播中！ 寒假模式已启动！你的生活主页面，从【教室】切换到了哪里？ 是燃系励志番、日常搞笑番，还是“摆烂”治愈番？ 这个假期，#寒假生存实录# 专属频道持续开放！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 📮 参与指南：两种方式，任你选择 🎬 方式一：评论打卡 · 速记名场面** 懒得开新帖？直接在 本帖评论区，用一句话或一张图，晒出你当日的“高光/崩坏瞬间”。 📖 方式二：深度连载 · 开启个人剧集** 欢迎 单独发帖，进行连载或深度记录。只需： 1. 在讨论区发布帖子； 2. 在 帖子标题开头 带上 #寒假生存实录# 话题，即视为成功参演。 ⏰ 放映期间：即日起 ~ 2月28日 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 互动奖励 🏆 人气打卡奖（TOP8瓜分奖池） 在 本帖评论区 打卡互动。活动结束后，符合评论要求&点赞数超过20的用户，将共同瓜分2016罐头！ ✨ 深度连载奖（优质内容激励） 在讨论区发表 #寒假生存实录# 主题的深度帖子。我们将根据内容的真实性、趣味性和故事性，评选出优质连载，送出稀有道具 「AC之神的祝福」 一张！ 🍀 随机幸运奖（全员参与抽奖） 所有有效参与者（包含评论打卡与发帖连载），均自动加入抽奖池！我们将随机抽取10位幸运儿，每人赠送 「昵称变色卡」 道具一张！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👉 往期话题 你的寒假日常，就是最真实的原创剧集。 快在评论区抛出你的“今日更新”，或开启你的专属连载吧！期待看到你的精彩“放映”。🎉

#创作计划#莫比乌斯反演

在此帖内，请不要刷罐！ 头图 补充说明左边是一个同班的（五年级）同学 @你好。 正文 本人来随便学点高级数论 （其实是乱翻《算法竞赛》），有错轻喷。 莫比乌斯函数 μ(n)={1n=1(−1)kn 是 k 个不同质数的乘积0n 含有平方因子\mu(n)= \begin{cases} 1 & n=1 \\\\ (-1)^k & n\text{ 是 }k\text{ 个不同质数的乘积} \\\\ 0 & n\text{ 含有平方因子} \end{cases} μ(n)=⎩⎨⎧ 1(−1)k0 n=1n 是 k 个不同质数的乘积n 含有平方因子 即： * 只要有 p2∣np^2 \mid np2∣n，就有 μ(n)=0\mu(n)=0μ(n)=0。 * 若 n=p1p2⋯pkn=p_1p_2\cdots p_kn=p1 p2 ⋯pk （pip_ipi 都是质数且所有数互不相同），则 μ(n)=(−1)k\mu(n)=(-1)^kμ(n)=(−1)k。 计算 因为莫比乌斯函数是积性函数（即 f(1)=1f(1) =1f(1)=1 且在 gcd(a,b)=1gcd(a,b)=1gcd(a,b)=1 的情况下有 f(a⋅b)=f(a)⋅f(b)f(a⋅b)=f(a)⋅f(b)f(a⋅b)=f(a)⋅f(b)），所以可以用在 O(n)O(n)O(n) 时间内预处理出所有 [1,n][1,n][1,n] 内的莫比乌斯函数值。 [1] 质数的 μμμ 为 −1-1−1。 [2] 如果一个数存在某个质因子的指数大于 111，那么它的 μμμ 值为 000 。 * 值得注意的是，只有当数存在最小质因子的指数大于 111 时，才会被直接筛为 000 * 其他情况则由公式 μ(d)=−μ(i)\mu(d)=-\mu(i)μ(d)=−μ(i) 完成，其中 ddd 是当前数，iii 是某个小于 ddd 的数 这种方法利用了积性函数的性质，使得每个数只被处理一次，从而实现线性筛。 示例 Python 代码： 基础恒等式 这个式子是可以证明的，只是没那么简洁，这里不贴了，想看可以点我。 ∑d∣nμ(d)={1n=10n>1\sum_{d\mid n} \mu(d) = \begin{cases} 1 & n=1 \\\\ 0 & n>1 \end{cases} d∣n∑ μ(d)=⎩⎨⎧ 10 n=1n>1 莫比乌斯反演 根据上方恒等式，可推出若两个函数满足： g(n)=∑d∣nf(d)g(n)=\sum_{d\mid n} f(d) g(n)=d∣n∑ f(d) 则有： f(n)=∑d∣nμ(d) g ⁣(nd)f(n)=\sum_{d\mid n} \mu(d)\, g\!\left(\frac{n}{d}\right) f(n)=d∣n∑ μ(d)g(dn ) 莫比乌斯反演例子 欧拉函数 已知： n=∑d∣nφ(d)n = \sum_{d\mid n} \varphi(d) n=d∣n∑ φ(d) 反演得： φ(n)=∑d∣nμ(d)nd\varphi(n)=\sum_{d\mid n} \mu(d)\frac{n}{d} φ(n)=d∣n∑ μ(d)dn 统计互质对数 ∑i=1n∑j=1n[gcd⁡(i,j)=1]=∑d=1nμ(d)⌊nd⌋2\sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)=1] = \sum_{d=1}^n \mu(d)\left\lfloor \frac{n}{d}\right\rfloor^2 i=1∑n j=1∑n [gcd(i,j)=1]=d=1∑n μ(d)⌊dn ⌋2 莫比乌斯反演例题 P2522 题目求的是 ∑i=xn∑j=ym[gcd⁡(i,j)=k]\sum_{i=x}^n \sum_{j=y} ^m [\gcd(i,j) = k]∑i=xn ∑j=ym [gcd(i,j)=k]，简单的类似二维前缀和的方法优化式子，然后消掉 kkk 变为 ∑i=1⌊nk⌋∑j=1⌊mk⌋[gcd⁡(i,j)=1]\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor} [\gcd(i,j) = 1]∑i=1⌊kn ⌋ ∑j=1⌊km ⌋ [gcd(i,j)=1]。 再变为 ∑i=1⌊nk⌋∑j=1⌊mk⌋∑d∣gcd⁡(i,j)μ(d)\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor} \sum _{d | \gcd(i,j)} \mu(d)∑i=1⌊kn ⌋ ∑j=1⌊km ⌋ ∑d∣gcd(i,j) μ(d)。 接下来交换求和顺序，在上述式子中，如果 ddd 要被枚举到，显然需要当且仅当 d∣id∣id∣i 并且 d∣jd∣jd∣j。所以把这个部分计入到贡献当中： ∑dμ(d)∑i=1⌊nk⌋[d ∣ i]∑j=1⌊mk⌋[d ∣ j]\sum_d \mu(d) \sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} [d \space | \space i] \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor } [d \space | \space j] d∑ μ(d)i=1∑⌊kn ⌋ [d ∣ i]j=1∑⌊km ⌋ [d ∣ j] 最后化简： ∑dμ(d)⌊ndk⌋⌊mdk⌋\sum_d\mu(d)\lfloor\dfrac{n}{dk}\rfloor\lfloor\dfrac{m}{dk}\rfloor d∑ μ(d)⌊dkn ⌋⌊dkm ⌋ 但是数据太强了，直接计算过不了，所以我们可以用到积性函数的性质做前缀和用 O(n)O(\sqrt n)O(n ) 的复杂度求解。 P2257 题目求的是 ∑i=xn∑j=ym[gcd⁡(i,j)∈Prime]\sum_{i=x}^n \sum_{j=y} ^m [\gcd(i,j) \in \text{Prime}]∑i=xn ∑j=ym [gcd(i,j)∈Prime]。 按照 P2522 的套路变为： ∑k∈Prime∑dμ(d)⌊ndk⌋⌊mdk⌋\sum _{k \in \text{Prime}} \sum_d \mu(d) \lfloor \dfrac{n}{dk} \rfloor \lfloor \dfrac{m}{dk} \rfloor k∈Prime∑ d∑ μ(d)⌊dkn ⌋⌊dkm ⌋ 发现过不了。 观察到复杂度高的原因是双求和导致的，并且 dkdkdk 重复出现了，所以可以令 T=dkT = dkT=dk。接下来，先枚举 TTT，显然 T≤min⁡(n,m)T \le \min(n,m)T≤min(n,m)。先把后面的那个部分写下来。再考虑会有多少的 μ()μ()μ() 会加在这个部分上。我们要让求的和的值等价不变，由于 d=T÷kd = T \div kd=T÷k，所以： ∑T=1min⁡(n,m)⌊nT⌋⌊mT⌋∑k∣T,k∈Primeμ(Tk)\sum _{T=1} ^{\min(n,m)} \lfloor \dfrac{n}{T} \rfloor \lfloor \dfrac{m}{T} \rfloor \sum _{k | T,k \in \text{Prime}} \mu (\dfrac{T}{k}) T=1∑min(n,m) ⌊Tn ⌋⌊Tm ⌋k∣T,k∈Prime∑ μ(kT ) 发现后面那个部分跟 n,mn,mn,m 没有一点关系了。所以这个求和被我们优化掉了。开个数组记录一下就可以了。 注意，交换求和的意义是将东西一起计算，我们通常都会把一些相同的东西给组合到一起，这样就可以离线处理一些东西，继而达到降低时间复杂度的意义。 我的这份 Python 代码由于语言本身较慢所以是无法通过的。 应该不会有人第一遍就发现代码里的小彩蛋。

# 官方题解 | 欢乐赛#66题解

官方题解 | 欢乐赛#66题解 赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目名称 题目难度 T1 皓仔的菱形 入门 T2 皓仔和水煮蛋 入门 T3 皓仔滑雪 入门 T4 皓仔的宝箱清点 入门 T5 皓仔的不降数 普及- T6 皓仔的水果筛选3 普及- T1 皓仔的菱形 题目大意 输出 555 行字符串，构成一个菱形。 题解思路 直接使用 cout 进行输出即可， 每一行结束使用 endl 换行。 参考代码 T2 皓仔和水煮蛋 题目大意 分支结构练习题，水煮蛋的黄金时间是 666 分 303030 秒, 现在一颗蛋已经煮了 xxx 秒，按照题目的要求进行判断并且输出， 规则如下： 1、如果还未煮 666 分 303030 秒，则告诉皓仔还需要经过 yyy 秒才可以得到一颗标准的溏心蛋， 输出数字 yyy。 2、如果恰好煮了 666 分 303030 秒， 输出 perfect。 3、如果时间超出 666 分 303030 秒， 输出 overcooked。 题解思路 按照题目思路编写多分支代码，为了方便的判断当前的蛋煮的时间是不足，恰好或是时间超出， 可以将目标时间 666 分 303030 秒 转化成秒数 390390390 秒。 而后进行判定， 当时间不足 390390390 秒时， 输出剩余时间 390−x390 - x390−x 秒， 时间恰好时输出 perfect, 当时间超过 390390390 秒后， 输出 overcooked。 参考代码 T3 皓仔滑雪 题目大意 皓仔想要去山上滑雪，滑雪的线路要求是一个单调不升序列：沿途高度始终不上升（后一个高度不大于前一个高度）。 现在给定一段路线的高度序列，请你判断这段路线是否单调不升 题解思路 题目要求整个数组单调不升，也就是说对于所有的 ai(2≤i≤n)a_i(2 \le i \le n)ai (2≤i≤n)， 都满足 a[i]≤a[i−1]a[i ] \le a[i -1 ]a[i]≤a[i−1]， 因此可以遍历 222 到 nnn， 如果有数字 iii 不满足 a[i]≤a[i−1]a[i ] \le a[i -1 ]a[i]≤a[i−1]， 可以直接输出 NO， 并且结束程序。 如果所有数字都符合要求则输出 YES。 参考代码 T4 皓仔的宝箱清点 题目大意 在一张 nnn 地图上，每个点都对应一个奖品价值， 并且还对应一个字符，当该点字符为 A 时， 可以获取该点的奖品价值。 问整个地图中所有可获取的奖品总价值是多少？ 题解思路 定义两个二维数组分别输入，其中字符网格使用字符数组 aaa，价值网格使用整数数组 ppp。遍历整个二维矩阵中的所有点(i,j)(i, j)(i,j)， 当 $a_{ij} == $ A 时，令答案加上该点的价值 vijv_{ij}vij ， 最后输出总答案。 参考代码 T5 皓仔的不降数 题目大意 当一个数字从高位到低位数字单调不降的情况下，该数字为 不降数。 现在给定一个数字 nnn， 请问在 1∼n1 \sim n1∼n 范围内一共有多少个 不降数。 题解思路 从 111 到 nnn 枚举所有数字，并且判定该数字是否是不降数。对于一个数字的判定，需要进行数位分解将其各个数位拆分出来，而后进行判断是否是一个不降数。每当出现一个不降数，答案加一，最后输出总体的答案。 参考代码 T6 皓仔的水果筛选3 题目大意 给定一个 nnn 个苹果，可以选择一批最大重量和最小重量差值不超过 yyy 的苹果一起打包出售， 问最多一次可以出售多少个苹果。 题解思路 本题可以采用双指针来进行解题， 首先对数组进行排序（复杂度 O(nlogn)O(nlogn)O(nlogn)），排序之后苹果的重量单调不降。 可以设定 iii 指针指向当前最小的苹果的重量， 在 aj−aia_j - a_iaj −ai 不超过 yyy 的情况下，使用最大的 jjj， 指向当前选择的最大的苹果的重量。 当 iii 变大向后移动的时候， jjj 也同样向后移动 ， 每次可以选择的苹果数量为 j−i+1j - i + 1j−i+1，在所有答案里面选择最大值并且输出。 参考代码

#寒假生存实录#寒假日记

致谢:不会C++的noah 灵感来源。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 期末日期:upd at 2026.2.4~5 DAY -开学第一天 交作业... .... DAY -114514....7891114514....7891114514....7891 DAY -SIN2XSIN^2XSIN2X 简单考一次数学 尝试拿满分awa 哈哈《满分》，用了我42min42min42min,真简单难 等待考试结果 ... ... ... ... .... 6，考了一般，屁股得烧红了qwq 寻找ACGO遗留的NOI小题... 水了几题 可恶，被神秘入嘲讽了 sleeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeep DAY -∞∞∞ 早上去了麦当当吃了美味的食物，happy! 中午的饭...难评 > 学习语文ing... 冲向理科高地，猛攻！！！ 我们班有几个入因为讨论三角洲然后被我们“善良”的牢湿狙击了 作业越来越多... 疯狂写作业中...流口水 最后一节课是体育课，我们班为了夺取体育课，我们派出了数学课代表和一大坨同学，结果全军覆没 我们班的同学现状: > 哈...数学....6...**** DAY −∞+1-∞+1−∞+1 作业好多,被迫学习，学习，学习，学习，学习，学习，学习，学习，学习，学习，学习，学习.... 我还是太可怜了awa 挑战洛谷的水题 DAY -∞+X∞+X∞+X 今天遇到一位小孩哥，他善良的说我跨楼梯，我直接白了一眼，但他太善良了，用它的爪子抓住了我的书包， 我只是轻轻地抚摸了一下，他就被我抽倒在地，眼睛直接飞了出去，然后有另外一个shazi叫来了一小坨蒟蒻， 我直接跟他进行了友好的交流， 他就吓哭了 能怪我吗？ DAY -6 日常生活，切了几道水题 DAY -5 想象着寒假的美好生活awa 我想的:美味的零食、美好的电脑、美好的旅行、美好的... 实际上:无穷无尽的作业、数不胜数的培训班... 落差好大啊! 水了一下ACGO的灌水池塘... DAY -4 正常的一天... RP++; 心中暗自乞讨分数 : ) DAY -3 也是在家中熬夜复习了一遍语文书qwq 看了91min91min91min,实际上只有67min67min67min才是真正的复习时间 我想考好啊... 祖宗保佑啊啊啊 爆切洛谷比赛，勉强拿下865865865分 DAY -2 上午烤语文,下午烤英语 语文烤试是9:009:009:00~10:4010:4010:40，时间还算充裕，勉强能写。 语文试卷一发下来直接大脑爆炸了，一道课外的古诗词题硬控我50min50min50min,演都不演了. 考试中: 8:55:拿到试卷，我去怎么题目这么多，有诈。 8:56:看到一道古诗词的题目，”课外积累:__________,___________“？有点难绷，想想想，想不出来，待会随便套一个吧 【基础】完成度：0，思考时间：2min 【现代文】完成度：0，思考时间：0min 【非联】完成度：0，思考时间：0min 【文言文】完成度：0，思考时间：0min 【作文】完成度：0，思考时间：0min 8:59:欸不是我怎么忘了古诗词格式怎么写了，得完了，QWQ。 9:00~9:19:闪击基础，除了那个课外积累别的没有了，还是easy 【基础】完成度：100，思考时间：18min 【现代文】完成度：0，思考时间：0min 【非联】完成度：0，思考时间：0min 【文言文】完成度：0，思考时间：0min 【作文】完成度：0，思考时间：2min 9:20~9:26:看看现代文，”穿越大草地“？猎奇，什么玩意？？？，但不多，还能做（不知道有没有伏笔） 看眼时间，WC怎么只剩1h22min了，我还要留50min写作文，赶紧写写写。 【基础】完成度：100，思考时间：18min 【现代文】完成度：100，思考时间：6min 【非连】完成度：0，思考时间：0min 【文言文】完成度：0，思考时间：0min 【作文】完成度：0，思考时间：2min 什么玩意，太猎奇了，思考3min,无果，跳跳跳，要没时间了。 【基础】完成度：100，思考时间：18min 【现代文】完成度：100，思考时间：23min 【非连】完成度：95，思考时间：11min 【文言文】完成度：0，思考时间：0min 【作文】完成度：0，思考时间：2min 9:50~10:05:什么玩意文言文还要写200字小作文？赶紧跳跳跳去写大作文吧 【基础】完成度：100，思考时间：18min 【现代文】完成度：100，思考时间：23min 【非连】完成度：95，思考时间：11min 【文言文】完成度：70，思考时间：15min 【作文】完成度：0，思考时间：2min 考完对答案选择题全对，古文也是轻松全对，但是阅读就错了一堆...希望上909090 考完直接一阵狂吃，然后狂泻,然后复习英语 中午的食物一般，还是沙威玛好呲 > 下午烤英语，有的紧张 > 英语试卷刚刚发下来，用了2s2s2s扫视了整张试卷，应该ok。用了几十分钟写完. > 跟别的入核对答案ing...幸好幸好...英语还好，起码没扣几分。 考试ing... 1:59:59拿到卷子 用3s3s3s看完题目,还挺简单的 【听力】完成度：0，思考时间：0min 【基础】完成度：0，思考时间：0min 【阅读】完成度：0，思考时间：0min 【作文】完成度：0，思考时间：0min 几分钟后... 什么玩意？这个图片好像似曾相识啊...是AI画的... ???让我写豆包？？？？****猎奇 【听力】完成度：100，思考时间：10min 【基础】完成度：100，思考时间：5min 【阅读】完成度：91，思考时间：13min 【作文】完成度：0，思考时间：0min 然后我们班有人打喷嚏像喇叭一样，啊哈哈哈哈，笑死我嘞. 完了，我忘记格式怎么写了，快动脑子啊啊啊 【听力】完成度：100，思考时间：10min 【基础】完成度：100，思考时间：5min 【阅读】完成度：100，思考时间：19min 【作文】完成度：99，思考时间：7min 想不出来了QWQ 哦！！！！我想到了，哈哈哈哈哈哈笑抽笑抽 希望明天的数学和科学能考好，保佑我啊啊QWQ 今晚想要尝试ABC 傲...好困期待明天，睡了... DAY -1 考的数学也都是肥肠的简单啊，期待明天 ButBUtBUT!!! 我数学错了一道111分的题目，气死我也！！！ 科学也就十几分钟写完了好吧嘻嘻嘻 可恶，有道题目给我卡了6min6min6min,脑袋要爆炸了awa 熬夜通宵的看电视 爽! \Huge 爽!~爽!  写作业................ 呜呜呜，我不想写作业啊啊啊(哈哈，我要写完了！((( 谁能帮我写寒假作业？ 今晚ABC好吧 不行了，我完CSGO匹配到了一群猪队友，我搁那口吐国粹，他们搁那卡住了，我直接蚌主了 DAY 0 嗯？ DAY 1 哈哈，洛谷大吉 早饭呲了一堆乱七八糟的食物... 写作业ing... 自己预估的成绩: 语文 数学 英语 科学 总分 考前预估 96 100 93 98 387 考后 92 100 92 97 381 实际上 -- -- -- -- -- 哎，买祝福真的需谨慎，千万不要乱贝者 啊 经过我的不懈努力，终于学会了截图QAQ 细节这一坨全是棕名 细节我绍兴一中的排名被轰炸到47了呜呜呜 发现一道可怜的黄题，肝到CE 啊啊啊啊，可恶 * 肝到黄题，卡了 * 肝到绿题，没了 不！！！！ 今日战绩: * AK P1493、P1498、P1477、P1469 * 70分:P1465、P1863、P1873 * 30分:P2028 * 10分:P3615 * 0分:P4026 这把肯定估值暴涨 被吓哭了 出成绩了AWA 语文 数学 英语 科学 总分 考前预估 96 100 93 98 387 考后 92 100 92 97 381 实际上 92 100 96 98 386 * 语文...一般，班级rk6 * 数学正常发挥，简单过百，rk1 * 英语超常发挥，班级rk2 * 科学无敌，班级rk1 去打lg的比赛咯 666，洛谷的那什么比赛没数据点？？？ 打了那么久，样例对了，结果输出直接UKE me: 链接直达比赛 我的思路 : [COCI 2025/2026 #4] 僵尸启示录 解题思路 问题理解 我们需要模拟 mmm 个僵尸从僵尸窝出发，沿直线向城市行进的过程： * 城市距离僵尸窝 nnn 米 * 僵尸速度：1米/秒 * 僵尸出发间隔：1秒（第一个僵尸在第1秒初出发） * 在路上有 kkk 个炸弹，每个炸弹有： * 位置 xxx（距离僵尸窝的距离） * 爆炸半径 rrr * 放置时刻 ttt（秒末） 当炸弹在时刻 ttt 放置在位置 xxx 时，会炸死该时刻位于 [x−r,x+r][x-r, x+r][x−r,x+r] 范围内的所有僵尸。 关键观察 1. 僵尸移动规律： * 第 iii 个僵尸在第 iii 秒初出发 * 在第 ttt 秒末，第 iii 个僵尸的位置为： * 如果 t<it < it<i：还在僵尸窝（位置为0） * 否则：位置为 min⁡(t−i+1,n)\min(t-i+1, n)min(t−i+1,n) 2. 时间范围： * 最后一个僵尸（第 mmm 个）最晚在第 mmm 秒出发 * 到达城市需要 nnn 秒移动时间 * 最晚在第 m+nm+nm+n 秒末可能到达 * 炸弹时间 t≤500t \le 500t≤500，题目保证足够 3. 问题规模： * n,m,k≤200n, m, k \le 200n,m,k≤200，暴力模拟可行 时间复杂度：O(m×(m+n)×k)O(m \times (m+n) \times k)O(m×(m+n)×k)，最大约 200×400×200=1.6×107200 \times 400 \times 200 = 1.6 \times 10^7200×400×200=1.6×107，可行。 起码我是这么想的 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 可怜的洛谷讨论区： 到了下午： 小小的本蒟蒻开始学习 报名了尼谷的课程，然后吃起了香香的泡面 开始刷题了QAQ e...好难啊 尝试卡常,好消息，前几个样例直接变成了绿色，最后一个TLE了 666，我的好心情瞬间消失一般 卡了几十次，电脑要卡废了，还是TLE 好消息：不是TLE！ 坏消息：是RE... 翻翻洛谷的陶片放逐： 666贴脸开大 因为有些过于猎奇我还是不放了 em... 接着刷题ing... DAY 2 嗯。 洛谷中平，还行 勉强能过。 随便呲几口面当早餐QAQ 下午还要返校。。。 回来了qwq,赚大了哈哈哈哈，学校里的积分直接718，唔哈哈哈 为什么你们不点赞了吗QAQ 我写的不好吗？ 好吧，把自己的评论放在下面，我有可能会把你挂在评论墙上: name say/problem Why DAY 3 哈 洛谷大凶 上午编程课啊啊啊 下午上奥数qwq 晚上还要英语课 呜呜呜，我好可怜啊 只能晚上更了... 加油啊啊啊，可怜的我 昨晚ABC忘说了,烂的一匹 今晚刷题 顺便开个盲盒 亏大了... 回来了em.... DAY 4 刚刚上完编程课，下午还有奥数课... 要连续上444天 今晚AWC DAY 5 发了AWC题解，然后开罐头赚了2发399，一发199，亏了133+100 QAQ，可怜的我下午还有奥数课...啊啊啊呜呜呜 我不想上啊啊啊 打了会儿州，跟老太对狙，护甲直接打爆了 玩了会儿MC，下了个亡者世界+畸变+光影+咆哮者+随机BOSS直接一个大洪水给我KO了 呜呜呜，我的钻石啊啊啊，我的护甲啊啊啊 还好没亏多少qwq

甜蜜/放松/惬意 强烈建议压力大时来一篇

其他版本小故事 这个帖子是什么 这个帖子写了很多故事，每个故事不存在连续性，强烈建议压力大时来一篇。 宇宙免责声明 本帖子没有不良引导，请理性观看 本帖子纯属瞎掰。 希望童瑞骐不会肘飞这个帖子 其中 trq 和瑞骐均是“cjdst”，zsr 和 思睿均是“cjdst9981”。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 下文转载自虎扑-沃尔玛神咪购物袋的评论，有较多删改，侵权可联系删除 机房的灯光昏暗，隐约透露出一丝危险的气息，zsr 踉跄着被 trq 拽了进来，小口喘着粗气， “瑞骐……瑞骐你停一停……” trq 的面色阴沉，将 zsr 甩在墙角，莹白的手腕被高举在头上禁锢，两人就这般无言对视。 原因无他，zsr 在打完 2025NOIP 后竟小声在 trq 耳边说了声， “瑞骐，我们断了吧。” 滔天的怒气在 trq 的胸口翻涌，顾及颜面，他只好将 zsr 拉到这昏暗的房间—— ——他怎么敢，怎么敢先对自己说分开，怎么敢忤逆自己，怎么敢抛下自己一个人面对一切！ 瑞骐不相信，也不接受他的 zsr 不要他了。 从未在人前流泪的 trq，竟然如孩童般泪如雨下，他的声音哽咽， “思睿，我……我哪里做的不好，你告诉我，我改，别说气话，别吓我，好吗？” zsr 只是低着头不语。 trq 拉着 zsr 的手，一滴泪滴在了 zsr 的手上， “思睿，你不会离开我的，对吗？” zsr 颤抖着回应，“是……” “我只是……只是好恨自己，恨自己连累了你的 2025CSP-S 分数……” trq 心疼地将他揽入怀中， “不要哭，思睿，不管成绩如何，我们都不会分开，嗯？” “嗯！” 他们在机房之外不弃不离，只有彼此。 ”思睿，答应我，我们一起打 ABC445 好吗“，trq 往 拉着 zsr 的手又紧了些。 “嗯” ...... 好了不闹了兄弟们，我和我目前认识到的的OI大佬距离拉近了耶/woo 最后，大家看个乐就好，重心还是要放在学习上哦。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Update In 2026/2/15 没看爽，再搬运一篇，来自虎扑-JR0664700732，有较多删改，侵权可联系删除。 （考场外的阳光仿佛吞噬一切，zsr 刚打完 2025NOIP，只想快点钻进车里。） 刚拐过转角，手腕就被人拉住了。zsr 抬眼撞进 trq 含笑的眸子里，他倚在墙边长身而立，外套搭在臂弯里，脸上带着阴恻恻的假笑。 “跑什么？”trq 的声音比走廊的风还低，他把人往怀里带了带，“等你很久了。” zsr 的耳尖瞬间烧起来，想往后退，后腰却抵上了冰凉的墙壁。trq 的气息混着淡淡的柠檬香氛漫过来，他低头，温热的呼吸扫过 zsr 的耳廓：“ 2025NOIPT1，DP 乱搞拿了 757575 分，是跟谁学的招数？” “我、我就是……”zsr 的声音细得像蚊子哼，手指无意识地揪着卫衣下摆。 trq 笑了一声，手托起 zsr 的下巴：“手抖什么？考场上做题的时候，怎么没见你怕？” 远处传来潘子涵说笑的声音，zsr 猛地绷紧身体，trq 却顺势把人往怀里又带了带，用自己的身体挡住了走廊的视线。他的下巴搁在 zsr 的发顶，声音压得更沉：“别怕，有我，他不敢对你做些什么。” 直到脚步声远去，zsr 才敢抬起头，却撞进了 trq 含笑的眼睛里。他刚想说话，trq 却忽然低头，在他嘴角飞快地啄了一下。 “奖励你的。”trq 退开半步，眼里是藏不住的笑意，“今天的比赛，打的不错。” zsr 的脸轰地一下红透，他把帽子拉得更低，莹白的细腻小手插进口袋，只听见 trq 在他头顶阴笑：“走了，下次带你打 ABC446。” 免责声明：本文乃搬运自虎扑-JR0664700732的评论改编而成，无不良引导，请读者理性阅读 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我被催更了 来自虎扑-虚构史学家虚照，有较多删改，侵删 帖子无不良引导，请理性阅读 楼梯间的灯光温温柔柔地裹着@Khalil，他看着考场外刚打完 2025NOIP 的 zsr ，指尖不自觉蜷了蜷。教练们满是夸赞，他望着画面里那个眉眼清软，小手莹白的人，下意识低低叹一句，语气自然得不像话： “我的 zsr。” 只有这一句，轻得像叹息，却精准落在所有教练耳里。 人群中瞬间炸开，数不清的声音密密麻麻涌上来，Khalil 才猛地回神，耳尖“唰”地烧红，慌忙跑出人群，心脏在胸腔里咚咚乱撞。他不敢回头，更不敢去想别的，只倚靠在墙角，安安静静地等那个人回来。 许久之后，通道口传来轻缓的脚步声。 zsr 拿着水杯，额前碎发被汗湿了一点，脸色带着赛后的红晕，眼神却软得像水。他一出来就看见 Khalil 站在那儿。瞬间耳朵烧的通红，神情又慌又乖，像只做错事的大型犬。 zsr 轻轻走过去，声音温软：“怎么了？” Khalil 没说话，手拖住了 zsr 的脸蛋，让录音播放在他耳旁，停在那句轻飘飘却分量十足的“我的 zsr”上。 zsr 盯着那四个字看了半晌，长长的睫毛轻轻颤了颤，原本火红的脸颊一点点漫上温柔的粉色。他没有笑出声，只是微微低下头，指尖轻轻勾住 Khalil 的手指，掌心带着微凉的温度，却甜得让人发软。 Khalil 喉结微动，低声问：“你……生气了？” zsr 轻轻摇头，抬眼时眼尾都带着甜意，声音轻得像耳语： “不生气，就是觉得，被你这样叫，我好开心。” 藏在心底许久的亲密，被一句精心编造的“口误”轻轻掀开，没有轰轰烈烈，却甜得漫过了整个赛场的灯光。 纯好听曲

#寒假生存实录#「失败/成功-我的成绩」

如果您是来刷罐头的：{\Huge 如果您是来刷罐头的：}如果您是来刷罐头的： 那么{\large 那么}那么 请 ️ ️本集标题： 「失败/成功-我的成绩」 ⚠分数： 学科 分数 成绩 最高分 排名 语文 100 92 97 NO.5-NO.10 数学 100 100 100 NO.1 英语 100 94 100 NO.5-NO.10 科学 100 100 100 NO.1 ✌总分： 总分 班级排名 386 NO.5 班级最高分： 分数 昵称（不透露真实姓名） 395 @BUG_花批（围观他的主页） 氛围BGM： 紧张气氛 能量值之表： 时间 能量值 Day-1（期末考第一天） ▮▮▮▮▮▯➡▮▮▮▯▯▯➡▮▮▮▮▮▮ Day-1（期末考第一天） ▮▮▮▮▮▮➡▮▮▮▮▮▮➡▮▮▮▮▮▮ Day-3（期末考结束第一天） ▮▮▮▮▮▮➡▮▮▮▮▯▯➡▮▮▯▯▯▯ Day-4（期末考结束第二天） ▮▮▮▮▮▮➡▮▮▮▮▮▮（附加▮▮）➡▮▮▮▮▮▯ Day-5（期末考结束第三天） ▮▮▮▮▯▯➡▮▮▮▮▮▮（附加▮）➡▮▮▮▮▮▯ Day-6（期末考结束第四天） ▮▮▮▮▮▮（附加▮▮）➡▮▮▮▮▮▯➡▮▮▮▮▮▯ Day-7（期末考结束第五天） ▮▮▮▮▮▮➡▮▮▮▮▮▯➡▮▮▮▮▮▯ 主线任务进展： 寒假作业： 时间 进度 Day-1（期末考第一天） / Day-2（期末考第二天） 20% Day-3（期末考结束第一天） 50% Day-4（期末考结束第二天） 98% Day-5（期末考结束第三天） 100% 也是在Day-5（期末考结束第三天）完成了寒假作业！ 寒假日记（前方高能） Day−1:{\normalsize Day-1:}Day−1: 8:00~12:00:语文考试，感觉良好，但有一题写了”毛**万岁“&”中华人民共和国万岁“也是929292分非常不好吧 1:00~3:00:英语考试，感觉良好，后面才知道作文要有格式（题目没说要格式！）也是949494分好吧，直接考砸，起飞！ Day−2:{\normalsize Day-2:}Day−2: 8:00~12:00:数学考试，感觉非常肥肠nice，随便乱写，也是100100100分好吧 1:00~3:00:科学考试，感觉良好，有一题目问腕关节则么运动：也是一直在那绕手腕好吧，100100100分照样拿下 Day−3:{\normalsize Day-3:}Day−3: 1:00~4:00:没啥感觉，出分数时*毛了，呜呜呜 Day−4:{\normalsize Day-4:}Day−4: 1:00~4:00:上香炉峰，扔雪球，快乐一天 Day−5:{\normalsize Day-5:}Day−5: 12:00~3:00:中午喝奶茶，吃云吞（云吞加太多醋不好吃），虽然云吞加太多醋了，但味道也是肥肠的nicenicenice!! Day−6:{\normalsize Day-6:}Day−6: 一天:直接赚爆，入账130￥ Day−7:{\normalsize Day-7:}Day−7: 12:00~1:00:买彩票，明日开奖（希望好运） Day−9:{\normalsize Day-9:}Day−9: 12:00~1:00:买彩票（刮刮乐），中了50元 Day−10:{\normalsize Day-10:}Day−10: 8:00~9:45（晚上）:买彩票（浙江6+1）等待开奖…… ⚡ 突发副本： 罐头：（每日记录）罐头：（每日记录）罐头：（每日记录） 时间 事件 Day-1（期末考第一天） 当”赌神 · 皮尔 · 卡松“失败，亏本400+罐头 Day-2（期末考第二天） 当”赌神 · 皮尔 · 卡松“成功，赚200+罐头 （没回本），数学期末考试有人睡觉睡着了 Day-3（期末考结束第一天） 当”赌神 · 皮尔 · 卡松“再次失败，亏本50+罐头 （但比一开始200个罐头好多了） Day-4（期末考结束第二天） 当”赌神 · 皮尔 · 卡松“照样失败，亏本133罐头 习以为常 Day-5（期末考结束第三天） 当”赌神 · 皮尔 · 卡松“失败，亏本133罐头 Day-6（期末考结束第四天） 当”赌神 · 皮尔 · 卡松“成功，直接1144罐头 Day-7（期末考结束第五天） 切水嘻哈赛，1700+罐头 Day-8（期末考结束第六天） 看白羊罐头日记不敢开 Day-9（期末考结束第七天） 看白羊罐头日记照样不敢开 Day-10（期末考结束第八天） 开罐头血赚 其他：（非每日记录）其他：（非每日记录）其他：（非每日记录） 时间 事件 Day-4（期末考结束第二天） 一书包零食，给班主任看蒙蔽了！哈哈哈 高光/崩坏时刻： 时间 具体事件 Day-1（期末考第一天） 脑抽忘记语文“日积月累”不会，写了”毛**万岁“&”中华人民共和国万岁“ Day-2（期末考第二天） 闲的没事干去找@BUG_花批玩，没想到刚考的科学分数100分！！！！！ （上次期末89分） Day-3（期末考结束第一天） 数学100分，曾在各科老师前发誓考不到100分倒立**，不用吃qwq,哈哈哈 Day-4（期末考结束第二天） 香炉峰，山顶打雪仗（对屋顶砸）（此处附加选项（2025/12/17）@BUG_花批宣读当乐子感言） Day-5（期末考结束第三天） 开王者荣耀没想到……我爸深藏不露有电玩小子……高贵皮肤！ Day-6（期末考结束第四天） 突然发现Aler这小子小号，大号都封了 未知出现 真的 我真棒——EMO……中 ️ ️经典台词： * 死手快写，死脑快想（emo……） * 疯子何尝不是另类的天才？ 彩蛋： * 数学100分，曾在各科老师前发誓考不到100分倒立**，不用吃qwq,哈哈哈（选自 高光/崩坏时刻-Day-3） @人时间到 @Daquavis MC @cjj(不加团) @BUG_花批 @༺དༀ༒∞░∞༒ༀཌ༻（不加团） @huangze @墨白渊作者本人 @昌振兴 @dream92143 @༺ཌༀཉི༒白·羊༒༃ༀད༻ @朱朗枫 @Gragher（不敢@怕被喷） 亿个小小建议链接描述

#寒假生存实录#寒假日记

如果您是来刷罐头的\HUGE{\COLOR{RED}如果您是来刷罐头的}如果您是来刷罐头的： 如果您还在刷\HUGE{\COLOR{RED}如果您还在刷}如果您还在刷： 真正好看的部分等春节过完的三天。我会写个特辑的捏。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 广子： 我与秋裤等人办的公开赛开始啦，欢迎大家参赛。链接描述 同时也欢迎各位加入出题团，具体内容看链接所指的帖子。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 特爱写日记。 其实我本来就想写的，然后看见了AC君的那个活动，虽然奖品不咋样但是还是参与了。 本文与秋裤的文章同步更新。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY -3 DAY -2 好的第一门语文。两个小时。前面水题，不过等交卷了突然感觉作文有点跑，不管了随缘吧。预估分数 95 考完语文立刻吃饭，后面在楼下玩了半个小时。中午没午睡，开始复习科学（临时抱佛脚这一块），做的是科学老师塞给我的一张卷子。 第二门科学，一小时四十分。题目难度不高，还行，不过写完感觉还是有点炸。预估分数 140，对完答案目前没有错的。 好的考完了，去吃饭。 然后听数学老师讲试卷。。。 我去阴死我了，晚自习下课没铃声导致晚回了五分钟，幸好老师不在 下半截晚自习做作业，不过主要是复习。然后看见俩哥们打起来了（桌子大残，椅子大残，空气大残），给我们班人都笑抽了（我去老师来了这俩娃都没事）。 回家水了一下犇犇，之后认真复习道法。 DAY -1 不是洛谷怎么大凶啊。 早自习直接复习数学。（不过数学老师呢 好的好的，数学考试，两个小时。嗯，水题……不是最后一题是个啥，咋还是原题的。倒数第二题又是个啥，本以为分类讨论结果只有一种情况（我还在答题卡划了重写一遍你知道吗）。看了一下至少五题是我做过的。居然原题大战有点意思。下课对完答案感觉良好。预估分数 118，对完答案目前没有错的。 原题大战原题大战。 依旧考完立刻恰饭，食堂也是个人物，关东煮美其名曰“麻辣烫”，骇死我里。 中午背道法背到冒烟你知道吗，还有英语老师突击检查你知道吗，还要写英语卷子你知道吗（我的 English 非常的 good ） eee，社会比我想象中简单，是我们社会老师监考。考试的时候老师一直在看我卷子知道吗，我心理压力多大知道吗，老师还翻来覆去的看知道吗。最后一道题实在不知道讲了啥知识点，干脆把已知的所有知识点默一遍吧，后面老师说看了我的答题卡，觉得我做的还行，感觉良好。预估分数 93（我们的卷子有个神秘的东西，想知道的私信我） 英语也还行，不过当我 20s 做完一个题目发现这题是听力的时候：。预估分数 115，没对答案、、（昨天晚上在南开的贴子里说英语来着）。 笑点解析：英语试卷的所有插图都是 AI 生成的，AI 味比@（坤泰）的代码还浓。后来我笔试部分都做完了听力都没放。做完听力+检查之后干坐一个小时%%% 关于这次期末考，列了张表大家可以看看（这里的预估分数是以最低的为准） 语文 数学 英语 科学 社政 总分 预估分数 95 118 115 145 93 568 实际分数 107 113 115.5 141 95 571.5 满分 120 120 120 150 100 610 完了怎么感觉考的跟shi一样（不管了相信玄学） 关于期末考，推荐更权威的渠道：去找滚蛋吧c++，同一张卷子他比我做的好。 我去我去，消失了一天的数学老师限时返场，送了我一袋子零食，开心死我了。 好的放假了。走之前和同学打了一会球，结果被数学老师狙了、 误闯天家劝余放下手中沙。现在罐头币两千多了，大赚。 准备闭关了，发现秋裤他们都红名了，就我和 Stars 还是橙名。而且 Stars 分还比我高。 笑点解析：猜猜撤回的消息是什么（ DAY 0 嗯？ return false DAY 1 嗯。 不是怎么起的比上学还早。 早饭一碗泡面，还是汤达人的。 今天和同学去玩，笑点解析：同学现在还在睡觉。十一点钟出发，去商场玩。一共八个同学。 今天开盲盒小亏。亏了 100。 在出去玩之前，出了一道题，和秋裤聊了一会天。 本来打算坐地铁的，结果我爸叫了个车给我送过去，在一个商场（上面有提到过）玩。八位同学来了六位。一个打王者一个打洲，其中跑刀哥跑了个显卡。跑刀子的那位给我们买了 KFC 大餐。吃完之后和其他人一起逛街去了。 一位同学（就是那位跑刀哥）拿着他的板去转转上估价，结果估出来 790。平还是加上了 91 元的补贴的。给那同学干红温了。 简单的解决了中饭，因为实在无聊买了个狼人杀。赢了两把输了一把 后来又完了猫鼠游戏，我太菜了就没玩。后面他们被俩女生干掉了，是我们班正副班长。 他们要吃晚饭走，我就算了，先行回来了。刚到家。 晚上搞了两口面对付对付。 一进书房看见我那堆积如山的课本/教辅陷入了沉思。话了 40min 的时间收拾完了。现在整洁多了（其他练习册都撇了）。我还特意留了两个没做过的教辅给我堂妹，我真是太善良了。 DAY 2 气死我了闹钟没关。 不过睡了一个回笼觉，七点四十分起床。第一件事就是回复秋裤的消息。 后来开了个盲盒， 的 BUG 给我卡掉了一个，但是记ACGO录里有一个 399，大概率我那个开了 399。今天盲盒小赚。 老妈给我做好了早饭，是排骨汤，很好喝。加上我爸前几天给我们卤味，味道挺好的。 成绩还没出 突然想起老师给我们布置的寒假作业还有一点点没写，明天就要交了，花了 5min 写完了（ 好的欢乐赛开始，赶紧水一波。 T1 我直接python三引号大法秒了，T2简单分支秒了，T3把单调不升序列的意思理解错了，吃了两发罚时，红温了，不打了。（最草率的一集） 好的成绩出了 语文 数学 英语 科学 社政 总分 预估分数 95 118 115 145 93 568 实际分数 107 113 115.5 141 95 571.5 满分 120 120 120 150 100 610 总结一下 * 语文：我去咋改的，可以可以很满意。班级 rk1 * 数学：我去咋改的，过程分我恨你啊。班级 rk3 * 英语：有点点差，申请加入义和团。班级 rk5 * 科学：也还可以，不过为啥扣这么多呢？班级 rk2 * 社会：可以的，正常发挥。班级 rk1 * 总分：比预料之中高，但是还是很可惜的，我感觉年级 rk1 拿不到了 555。班级 rk1…………我就知道，年级 rk2。555555 综上所述：数学过程分我恨你 555 彻底红温了。 为了缓解心情，和秋裤哥一起做了一些水题。比谁卡常卡的好。好消息：我卡到了 8ms；坏消息：是错的；更坏的消息：加上一个 if，代码能过但是复杂度瞬间增加 30ms——有人知道什么原因吗QAQ。 滚蛋吧c++限时返场 细节秋裤找了1h 的题目。 和秋裤比赛切题，最终战绩： * 我：三道橙题（AC）+一道黄题（50pts）+一道绿题（在时间结束前拼死跳出的暴力，25pts） * 秋裤：一道橙题（AC）+ 一道黄题（50pts）+一道绿题（20pts）。他策略失误了，我现切三个橙，然后拿部分分。他先做黄去了。 简单洗了个澡，明天要返校，早点睡觉吧。 今日做题战绩（参考秋裤的）：P5266 P14635 P1190 P11908 P1028 P3114（50pts） P7074（25pts） DAY 3 误闯天家，三个 888，两个 99，大赚！！！！！ 今天要返校了，一天安排都很紧，只有等晚上来写了QAQ。 好的返校回来了，中午午饭简单凑活了一下。 下午回了一趟小学，见了一下曾经的班主任。当时正值雨季，漫步在园中的校园，让我想起了过往的许多美好回忆。所以…… > 我常常追忆过去。 > > 生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。 > > 云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己>的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。 > > 追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。>但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。 > > 过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。 > > 我该在哪里停留？我问我自己。 （（（ 和许多曾经的同学聊了会天，之后我们聚在一起拍了一张合照。再然后，我们和老师聊了。但是因为个人原因，我不得不提前离开。走之前回望校园，想起了在小学的时光。 我常常追忆过去。说句实话还是有点挂念，下次再回来看看吧。 好的来和秋裤比赛了。 上来两个水体，一个打表一个二分答案板子。后来看见一个黑题，想尝试部分分。结果死磕半小时， O(t×n)O(t\times n)O(t×n) 的算法一分都不给，气死我了气死我了。 最后力竭了先行下场。 和 Xy，秋裤讨论了一下关于公开赛的事 因为 smart luogu 不适配新版洛谷界面，下了氧洛谷，再稍微配了一下。效果挺不错的。 晚上吃了一锅纯素的火锅。 不是今天怎么就有打卡了啊，不管了看见地理的填图量很少直接 5min 写完上交。666 还有读英语、体育。 简单看了一会电视，准备来水讨论拉 今日刷题记录：P2063：0pts P2440:100pts P8738：100pts DAY 4 不是不觉已经放假 4 天了，再过二十多天就要上学了（ 今天自然醒 每日开罐头，小亏 100 罐头币 早饭没饭吃，依旧吃泡面。 上午一直在上课+写作业 到小码王了 上课了，今天上的内容是图的遍历，难度还行。 气死我了调了半天是我思路错了、、、 买了五个盲盒，一次买五个，明天直接梭哈。对了，注意到码豆商城也有冰箱贴了，而且价格还相等。 It's been a long day,without you my friend. 《一天一篇作文》555 今晚 ABC 真毒瘤，感觉要掉分了。 DAY 5 坏了坏了，今天盲盒开完亏了 500 多。 中午的饭还可以的捏。 去小码王的路上碰见两个同学。一个小学的一个初中的。 神秘滚c上课练习切屏技术，只是为了补作业、、、 今天的内容是拓扑排序，感觉不难的。善良的老师还给我们买了饮料，大方地说随便喝。老师还是太好了。 回来之后简单玩了一会，写了一篇作文一篇阅读的作业。 晚上吃剩菜剩饭捏。反正没一样是现炒的，全是微波炉里热的呃呃呃。 又来写作业了。 今天的洛谷月赛怎么这么毒瘤，T1 最终拿了 15 分，这还有一千五百名能拿。 DAY 6 哦原来昨天比赛是黄绿蓝紫啊，那没事了 洛谷估值才加了 2 分，看来我离红名还远着呢。 今天盲盒大赚 500 罐头币，相当于把昨天亏得赚回来了。还是没开到我想要的 1999。 AtCoder 的 AWC 感觉挺有意思的，毕竟是 un，今晚打打看。 早上吃了一盘煎饺，好吃捏。 今天怎么又有一篇作文 看秋裤他们和2778超燃智斗。 今天去我妈公司那里吃了顿中饭 AWC？ 今天小码王内容是并查集，幸好我提前学了，非常轻松捏。 我们班有五个人，除了我之外都会切屏大法，吓哭了。 神秘滚c切屏被老师捉了 我去小码王这么大方给我们喝饮料，分水果还一人给我们一个春联（虽然我也不会贴这个的QAQ），这么好。 推荐刷题时放《千与千寻》，纯音乐版本，最好是陶笛演奏的，最后开 0.9x。个人感觉在刷题的时候听很好。 今天晚上来做做AWC 不是你们点赞我可以理解，但是你点十几个赞我就不理解了。这是骚扰，骚扰知道吗[愤怒][拍桌子] 坏了 AWC 就出来了前三题，还是太菜了。等我课程结束了我要闭关学新算法了，不然今年 CSP 要炸。 笑点解析：本场比赛允许使用 AI。 已严肃阅读帅童的 AWC 题解。 DAY 7 罐头币 5000 祭！ 为什么我开了这么多轮一次 1999 都没有。 今天没有作文（喜） 但是要上小码王（悲） 今天中午我姑姑他们来做客捏 今天小码王上的是最小生成树。今天是整个寒假里最后一节小码王了。 还行，题目都是板子，不难。 好的滚c左边那位同学用毕生积蓄抽了一个赌神盲盒，最终以 66 个的稀有战绩收场。 下课啦。 （跟踪滚c失败 不是啥阴，做一次地铁见一次同学是吧，还次次不重样，怀疑他们卡好时间来蹲我。 坏了就是冲着我来的（欸我明天不上小码王 其实，忘川秋库是 M。理由见此：链接描述 和秋裤做了好多题目，一共 15 题，数不过来了就不一一列举了。 一个 sib 天天抄我头像，可以看这里：链接描述。现在用马达加斯加的企鹅了。记得这图好像是洛谷截的。 米兰冬奥会捏。昨晚看到十点半。然后电视炸了、和我爸修。修完就睡觉了。 DAY 8 day 7 day 8 今天盲盒梭哈，只赚了 200 多个，为什么你们都能开出来 1999 啊，此时的我： ACGO 铃铛老是炸，怎么老被炸啊。发现一看全是刷罐头的，我真无语了，你们刷罐头的能不能消停一下，我真服了。 今天没有作文（喜）。 上完语文课了（喜） 没饭吃了（悲），呜呜呜，又是吃泡面的一天。但是泡面很好吃（喜）。 开始做题，找了一些黄/橙的贪心做做，联系下思维。 下午说要和我做题神秘秋裤不见了，所以： 神秘秋裤刚上线就走了，真是个神入。气死我了 6 秋裤一会上线一会下线，我直接在电脑旁边写作业了。结果他骂我 sib，555. 我就知道，私信 99+，一定是sib忘川秋库搞的鬼。然后跟忘川秋库刷屏，从 ACGO 刷到洛谷，从百草园刷到三味书屋（ 然而还是我更胜一筹，顺便骂了两句秋裤。 好的吃饭去了 晚上没菜吃整了四根香肠awa。 sib秋裤又给我私信炸了，气死我了。 米兰冬奥会。 sib 秋裤搞了个连点器刷我屏，后面给他拉黑了。让他受着 DAY 9 我人还是太好了，给秋裤解除拉黑了。 今天早上一碗年糕，好吃喵。 今天盲盒梭哈，5 个 199，我无语了，看来赚到 10000 还是很遥远的事了。 弄了这么多高雅人士显得我很 sib。但是我就弄 今天还是没有作文，嘻嘻嘻嘻。 关于我的背景：经典咏流传，我必须改名字。 请输入文本 要过年啦，也一页一页一页哦哦，笑点解析（对面是 wcqk）： 话说我真的越来越抽象了吗？ 中午吃了一个肉夹馍+一碗瘦肉丸。好吃好吃。 回来写了会作业，同时和秋裤聊天。准备基础赛。 基础赛 A 脑子抽抽吃了 5 发罚时，然后先把 B 做了。做完之后 A 也好了。 接下来跳了 1h 的 C 无果去和隔夜水了。 最终战绩： (100+100+20)pts(100 + 100 + 20) pts(100+100+20)pts。 神秘秋裤切出了 C，尝试查看他的代码结果出来滚木。所以简称滚C。 写作业去了。 宣传捏 晚上吃了老妈炖的牛骨汤。就是这个牛骨髓给我赤兔了、太击败腻了。但是其他的肉都是很好吃的。加上其他菜，这顿晚餐： 吃完饭练字捏。 练完啦，可以看电视啦。 证明题做多的忘穿秋裤尝试证明所有人都是非男： > 引理：1、所有男人都有格调 2、格调是可导的 3、格调是等插的 > 三个引理是显然的，不再证明 > 记一个人的格调数目随时间变化的函数为 f(x)f(x)f(x) > 假设存在一个男人，他的格调数目在某一时刻大于 000，即存在 x0,f(x0)＞0x_0,f(x_0)＞0x0 ,f(x0 )＞0 > 记这个男人的寿命为 lll，因为他在受精卵时期即死亡时刻不具备有生理活性的格调，易得 f(0)=0,f(l)=0f(0)=0,f(l)=0f(0)=0,f(l)=0，且对于x>l,f(x)=0x>l,f(x)=0x>l,f(x)=0 > 当p为非负整数时，记 f(p)f(p)f(p) 组成的数列为 ap{a_p}ap ，由引理 333 知 ap{a_p}ap 为等差数列，又由 a0=0,a[l+1]=0a_0=0,a_[l+1]=0a0 =0,a[ l+1]=0，易知a_p=0，（中括号为高斯函数，为保证下标为整数） > 取任意 p0∈N∗p_0∈N*p0 ∈N∗,所以 f(0)=0,f(p0)=0f(0)=0,f(p_0)=0f(0)=0,f(p0 )=0 > 记 f((p0)/q)f((p_0)/q)f((p0 )/q)，其中q为正整数组成的数列为 bq{b_q}bq ，同理知b_q=0,即f((p_0)/q)=0 > 由于 p0p_0p0 是任取的，我们知道，对于 x∈Q∗x∈Q*x∈Q∗，f(x)=0f(x)=0f(x)=0 > 由引理 222 知，f(x)f(x)f(x) 是可导的且连续的，因此对于 x∈R∗x∈R*x∈R∗，f(x)=0f(x)=0f(x)=0 > 即，这个人的格调数量在任意时刻等于 000，这与假设冲突 > 因此，世界上没有一个男人具有格调，根据引理 111 知，没有格调的人不是男人 > 因此，所有人都非男，证毕 我要暴打皓仔，暴打欢乐赛。大炮打蚊子（ 大水欢乐赛快速 AK 变换，可惜吃了一发罚时。 晚上写欢乐赛题解，结果听到狼叫，给我吓哭了。不过后面没有了。 踏马的是人在叫。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY 10 早密码，五个盲盒全是九十九，亏死我了。 我的洛谷题解过审啦，太棒了。 还是没有作文（喜） 不是怎么调戏反作弊系统也要被棕啊，昨天月赛我就想干这事来着 吓哭了。 神秘滚c上线刷罐头 今天我奶奶他们又来玩了，111 带俩小孩出去玩。 看了忘川秋库给我发的猴子工单，太爽了必须共享。 这一个秋裤一个Stars 这俩人 中午饭真好吃捏。 我怀疑客服们都用了亲亲亲插件（喵喵喵插件），刚刚试着和忘穿秋裤这样说话给秋裤弄红温了，自己也绷不住了、、以后绝对不当客服。 晚饭吃剩菜、 门口有三位人和警察蜀黍吵起来了，不知道什么原因，然后我就坐在窗前吃瓜。 很神秘 DAY 11 尼玛怎么还是亏得，昨天不是大亏了一波吗，下次再也不五个梭哈买了，后面我分批买。 今天大扫除捏。 早上吃了一碗水煎饺，好吃好吃。 大扫除#1——擦玻璃 科技改变生活喵，现在都有擦玻璃机器人了。我们的阳台窗特别大，再也不怕擦玻璃累成狗了（ 这机器人还可以擦窗玻璃的外侧捏。我妈告诉我一个小技巧，在擦的时候喷点酒精，这样子擦完就没有印子，确实如此捏。 就是擦得有点慢捏，但是还是很方便的，还有自动寻路功能。 照片就不放了，我怕秋裤给我开户（ 我去我要擦全部的玻璃，至少擦一上午（甚至擦不完www） 沃德发，还真擦了一上午，还没擦完问题是 骇死我里 擦到下午两点 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 捉到滚C拉，www 和神秘秋裤聊了一会天，然后下了。 DAY 12 不是官方条概率了把，我都连亏四天了甚至一个 399 都没出过，我去。 早饭依旧煎饺。 去了趟医院，火速回归。 好的出发去买年货捏。 买了零食大礼包，四箱特能输，还有一堆薯片，瓜子之类杂七杂八的东西，花了小一千。 中午吃了个快餐，蹭了一点点可乐。 我爸要洗车，跟着去洗，是自助洗车。本来想帮忙但是被高压水枪冲成sib了，只能去晒太阳了。 后来还是帮上忙了，来擦车，甩毛巾。 我把上班去了，我们自己坐地铁回家。 一到家就看见一堆点赞，不用想一看就是刷罐头的。 还真是。 秋裤拉着我刷题，但是我要写作业，委婉的回绝了（ 打算寒假去湖北一趟，看看能不能见到秋裤。 神秘电脑突然关机，吓死我了。 作业写死我了。 简单放松一下，吃了过年吃的瓜子+南瓜子+开心果，太开心了。 DAY 13 密码的连亏五天 CXXP#1 开始了，看着 Lost 大佬 AK。 去买东西了 买了一堆海鲜还有各种菜，做年饭。我们这里是中午吃，叫做年饭，秋裤也是的。 买完回来了捏。 处理一下 CXXP#1 的事情 坏了被叫走当黑奴了，切蒜末去了。 呛死我了，终于切完了 吃年饭了捏。 好吃好吃，继续来 CXXP#1 当黑奴。 今天是二十一世纪的第 9178 天。 吃剩菜。 看春晚捏。 省流，春晚的标志是春晚四叠马。 我和你同时掉河里你就被电四了。 现在机器人越来越强了，后空翻都会了。 欸你换新手机了，旧的呢 旧的我放在（）（） 撇了！！！！！撇了！！！！！ 新年快乐！\HUGE\COLOR{RED} 新年快乐！新年快乐！ 密码的尝试抢洛谷第一发题解，交上去发现我这个电脑时间不准，密码。 DAY 14 如你所见这是半夜写的，至少这句是半夜写的。 盲盒终于赚了，888 一个，555 我太可怜了。祝各位新年都能 888 捏。 难忘今宵 饿啊睡醒了。 简单吃个早饭 出发去金华 没拍路上的风景，返程给你们拍。 笑点解析：去服务区上厕所，看见一个女的走到男厕所里去了，后来被保洁阿姨赶出来了、 中午 12:30 到，吃了一顿丰盛的中饭。 亲戚们都来了，和与我年龄相仿的人一起扎鞭炮，扎窜天猴的时候窜天猴飞我脚上了，吓哭了。 没事。 炸沙子，扎砖块这一块。 打扑克捏。 好的还是我赢得多。 耶耶耶收压岁钱了，才第一天就收了好多红包了。 《兵不厌诈》《暗度陈仓》 DAY 15 今天盲盒小亏 去祭祀了，祭拜祖宗。有图，等会给你们放。 走在乡间的小路上。 中午饭特别好吃，在外太婆家吃的（PS：外太婆是外婆的妈妈）。 回家喽、 舅妈他们也来了，我们暗度陈仓在严禁卖烟花的地方买了烟花，其实也不算严禁，这里的话就算警察看见了他也不会来管你，但是总有写喜欢fanjian'的人来举报，这个时候警察就不得不管了，所以每个商贩都把烟花藏起来，等有人来买的时候再拿出来。 我们买了整整一箱子。花了 500. 晚上吃火锅，和他们买火锅底料。顺带买了两盒草莓，还可以的。 继续当魔丸玩窜天猴，为什么说是魔丸，因为我窜天猴不往天上放，去炸沙子，炸枯树之类的东西。我们研究了一个好玩的，就是把窜天猴的尾巴扯掉，之后塞到摔炮的盒子里，严严实实的埋在沙堆里。到时候一点，点完之后把石头压上去。最后你会得到——自己去试试把（ 笑点解析：撒尿牛丸是鸡肉+猪肉调配而成的的，他吗一点牛肉的影子没有 什么满级黑心商家、、、 尼玛 洛谷你不乘哦。 晚上吃火锅捏。像我这种湖北的肯定要吃辣锅啊——我k怎么这么辣。 原来是底料没化开，吃了满口底料。后面就不拉了 一起放烟花啦。 放完了，准备读博，用扑克牌。 前面马上输完了，后面翻盘了。稍微赚了一点点。 DAY 16 早上起得很晚。 吃中饭ing 回家了。 到家在 3:30，比预测的时间快乐 30min。 简单玩了一会，吃完饭。 吃完晚饭立刻去看《飞驰人生3》，很好看，推荐大家去看。 看完回来九点，看了两个小时的电视，警匪片。 晚上十一点睡觉。 DAY17 起床了。 吃饭了。 写作业。 今天是我弟的生日捏，开心捏。

【学习笔记】拉格朗日插值入门

同步发布于 我的 cnblogs 这篇应该比较简单（） LAGRANGE 插值 > 给出 nnn 个点 (xi,yi)(x_i,y_i)(xi ,yi ) 满足 xi≠xjx_i\neq x_jxi =xj ，可以唯一确定一个 n−1n-1n−1 次多项式 y=f(x)y=f(x)y=f(x) 过上述所有 nnn 个点。 > > 现在给出 kkk，求 f(k)f(k)f(k) 的值。 一个简单的想法是直接 Gauss 消元，可以 O(n3)O(n^3)O(n3) 解出这个 n−1n-1n−1 次多项式每一项的系数。 这里介绍一下用 Lagrange 插值的解法： * 构造 nnn 个函数 fi(x)f_i(x)fi (x) 表示该函数过点 (xi,yi)(x_i,y_i)(xi ,yi )，对于任意 j≠ij\neq ij=i 都过点 (xj,0)(x_j,0)(xj ,0)。容易发现令 f(x)=∑i=1nfi(x)f(x)=\sum\limits_{i=1}^nf_i(x)f(x)=i=1∑n fi (x) 就可以得到一个满足条件的函数 f(x)f(x)f(x)。 * 然后考虑构造因式分解：对于每个 fi(x)f_i(x)fi (x) 多项式构造一项 x−xj(i≠j)x-x_j(i\neq j)x−xj (i=j)，然后凑一个系数 aia_iai 满足 fi(xi)=yif_i(x_i)=y_ifi (xi )=yi ，容易解方程得到 ai=yi∏j≠i(xi−xj)a_i=\dfrac{y_i}{\prod\limits_{j\neq i}(x_i-x_j)}ai =j=i∏ (xi −xj )yi 。 * 于是有：f(k)=∑i=1nfi(k)=∑i=1nyi∏j≠ik−xjxi−xjf(k)=\sum\limits_{i=1}^nf_i(k)=\sum\limits_{i=1}^ny_i\prod\limits_{j\neq i}\frac{k-x_j}{x_i-x_j}f(k)=i=1∑n fi (k)=i=1∑n yi j=i∏ xi −xj k−xj ，可以在 O(n2)O(n^2)O(n2) 的时间复杂度内求解。 :::success[O(n2log⁡n)O(n^2\log n)O(n2logn) 解法] ::: :::success[O(n2)O(n^2)O(n2) 解法] ::: 001. P5667 拉格朗日插值2 根据上面的理论，容易得到： f(m+k)=∑i=0nyi∏j≠im+k−ji−jf(m+k)=\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}\frac{m+k-j}{i-j} f(m+k)=i=0∑n yi j=i∏ i−jm+k−j 可以 O(n2)O(n^2)O(n2) 时间复杂度求解。 考虑对这个东西进行优化。注意到 kkk 的取值是连续的一段，所以从这里突破： f(m+k)=∑i=0nyi∏j≠im+k−ji−j=∑i=0nyi∏j≠i(m+k−j)∏j≠i1i−j=∑i=0nyi(m+k)!(m+k−n−1)!(−1)n−i1i!(n−i)!(m+k−i)=(m+k)!(m+k−n−1)!∑i=0nyi(−1)n−i1i!(n−i)!(m+k−i)=(m+k)!(m+k−n−1)!∑i=0n[1i!×yi×(−1)n−i1(n−i)!]×1m+k−i\begin{aligned} f(m+k) &=\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}\frac{m+k-j}{i-j}\\ &=\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}(m+k-j)\prod\limits_{j\neq i}\frac1{i-j}\\ &=\sum\limits_{i=0}^ny_i\frac{(m+k)!}{(m+k-n-1)!}(-1)^{n-i}\frac1{i!(n-i)!(m+k-i)}\\ &=\frac{(m+k)!}{(m+k-n-1)!}\sum\limits_{i=0}^ny_i(-1)^{n-i}\frac1{i!(n-i)!(m+k-i)}\\ &=\frac{(m+k)!}{(m+k-n-1)!}\sum\limits_{i=0}^n\left[\frac1{i!}\times y_i\times(-1)^{n-i}\frac1{(n-i)!}\right]\times \frac1{m+k-i} \end{aligned} f(m+k) =i=0∑n yi j=i∏ i−jm+k−j =i=0∑n yi j=i∏ (m+k−j)j=i∏ i−j1 =i=0∑n yi (m+k−n−1)!(m+k)! (−1)n−ii!(n−i)!(m+k−i)1 =(m+k−n−1)!(m+k)! i=0∑n yi (−1)n−ii!(n−i)!(m+k−i)1 =(m+k−n−1)!(m+k)! i=0∑n [i!1 ×yi ×(−1)n−i(n−i)!1 ]×m+k−i1 记 Pi=(m+i)!(m+i−n−1)!,Ai=1i!×yi×(−1)n−i1(n−i)!,Bi=1m+iP_i=\frac{(m+i)!}{(m+i-n-1)!},A_i=\frac1{i!}\times y_i\times(-1)^{n-i}\frac1{(n-i)!},B_i=\frac1{m+i}Pi =(m+i−n−1)!(m+i)! ,Ai =i!1 ×yi ×(−1)n−i(n−i)!1 ,Bi =m+i1 ，则可以用 NTT 求出 C=A⊙BC=A\odot BC=A⊙B 即 CCC 为 A,BA,BA,B 两个序列的等差卷积，而 PiP_iPi 显然可以线性递推。 但是这真的对吗？？？把卷积形式写出来之后发现其形如：Ck=∑iAiBk−iC_k=\sum\limits_iA_iB_{k-i}Ck =i∑ Ai Bk−i （0≤i≤n0\le i\le n0≤i≤n），这怎么还出来负数下标了（）不过解决这个问题也是简单的，重新记 Bi=1m+i−nB_i=\frac1{m+i-n}Bi =m+i−n1 ，此时有 Cn+k=∑i=0nAiBn+k−iC_{n+k}=\sum\limits_{i=0}^nA_iB_{n+k-i}Cn+k =i=0∑n Ai Bn+k−i ，将其写成卷积的形式只需要对所有 i>ni>ni>n 都记 Ai=0A_i=0Ai =0 就可以扩展为 Cn+k=∑i=0n+kAiBn+k−iC_{n+k}=\sum\limits_{i=0}^{n+k}A_iB_{n+k-i}Cn+k =i=0∑n+k Ai Bn+k−i 的形式。 一次 NTT 卷积即可求出 C=A⊙BC=A\odot BC=A⊙B 这个等差卷积。 因此总时间复杂度为 O(nlog⁡n+m)O(n\log n+m)O(nlogn+m)，分段打表阶乘可以把后面的 O(m)O(m)O(m) 省去。 跑了 973ms，喜提最劣解（没事至少这个能过） :::success[Code] ::: 006. CF622F THE SUM OF THE K-TH POWERS 通过作差可以发现答案是一个 k+1k+1k+1 次多项式的形式，因此想到 Lagrange 插值。将 xi=ix_i=ixi =i（0≤i≤n0\le i\le n0≤i≤n）带入，有： ∑i=0nyi∏j≠ix−ji−j=∑i=0nyi(∏j=0i−1x−ji−j∏j=i+1nx−ji−j)=∑i=0nyi(∏j=0i−1(x−j)∏j=i+1n(x−j)∏j=0i−11i−j∏j=i+1n1i−j)=∑i=0nyi(−1)n−i1x!1(n−x+2)!∏j=0i+1(x−j)∏j=i+1n(x−j)\begin{aligned} &\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}\frac{x-j}{i-j}\\ =&\sum\limits_{i=0}^ny_i(\prod\limits_{j=0}^{i-1}\frac{x-j}{i-j}\prod\limits_{j=i+1}^n\frac{x-j}{i-j})\\ =&\sum\limits_{i=0}^ny_i(\prod\limits_{j=0}^{i-1}(x-j)\prod\limits_{j=i+1}^n(x-j)\prod\limits_{j=0}^{i-1}\frac1{i-j}\prod\limits_{j=i+1}^n\frac1{i-j})\\ =&\sum\limits_{i=0}^ny_i(-1)^{n-i}\frac1{x!}\frac1{(n-x+2)!}\prod\limits_{j=0}^{i+1}(x-j)\prod\limits_{j=i+1}^n(x-j) \end{aligned} === i=0∑n yi j=i∏ i−jx−j i=0∑n yi (j=0∏i−1 i−jx−j j=i+1∏n i−jx−j )i=0∑n yi (j=0∏i−1 (x−j)j=i+1∏n (x−j)j=0∏i−1 i−j1 j=i+1∏n i−j1 )i=0∑n yi (−1)n−ix!1 (n−x+2)!1 j=0∏i+1 (x−j)j=i+1∏n (x−j) 后面这两个 ∏\prod∏ 一看就很能预处理，而前面的显然可以直接算。时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)。注意到 iki^kik 是积性函数，所以使用线性筛可以将其优化至严格 O(n)O(n)O(n) 求解。 007. P4593 [TJOI2018] 教科书般的亵渎 设 S(n,k)=∑i=1nikS(n,k)=\sum\limits_{i=1}^ni^kS(n,k)=i=1∑n ik，则容易观察到该题要求的答案为：∑i=0mS(n−ai,m+1)+∑i=0m∑j=i+1m(aj−ai)m+1\sum\limits_{i=0}^mS(n-a_i,m+1)+\sum\limits_{i=0}^m\sum\limits_{j=i+1}^m(a_j-a_i)^{m+1}i=0∑m S(n−ai ,m+1)+i=0∑m j=i+1∑m (aj −ai )m+1。后半部分可以暴力快速幂求解，而前半部分是 CF622F，直接套用上面的公式求解即可。