全网最详细赌罐头教程重磅来袭！

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 666登上榜一了 > 此贴持续更新中，每十天会更新一次总概率 作为一个已经赌过25次罐头的人，我认为有必要写一篇教程，造福人类，让大家不当守财奴！ 本人已经买过25次“AC之神的祝福”，得出数据如下： 我的收益：901⇒2567\color{red}我的收益：901\Rightarrow2567我的收益：901⇒2567 收益率：约为185%\color{red}收益率：约为185\%收益率：约为185% 注：以上数据包含我每日点赞、评论、做题得到的罐头，但去掉后收益率也不低于170%170\%170% 以下是详细数据： 25次中： 66：222次，8%8\%8% 99：555次，20%20\%20% 199：121212次，48%48\%48% 399：333次，12%12\%12% 888：333次，12%12\%12% 可以看出，概率排名为： 199>99>399=888>66 但是！根据我的经验，不止这么简单，于是我们分析我每天的收益： DAY 1 199三个+399一个+888一个，总收益889，收益率89%89\%89% DAY2 66一个+99四个，总收益-533，收益率−53%-53\%−53% DAY 3 199五个，总收益0，收益率0%0\%0% DAY4 66一个+199两个+399一个+888一个，总收益756，收益率76%76\%76% 需要说明的是，我这次是先买了四个，开完后又买了一个\color{red}需要说明的是，我这次是先买了四个，开完后又买了一个需要说明的是，我这次是先买了四个，开完后又买了一个 DAY5 99一个+199两个+399一个+888一个，总收益789，收益率79%79\%79% 需要说明的是，我这次是先买了三个并开完，开完后又买了两个并开完\color{red}需要说明的是，我这次是先买了三个并开完，开完后又买了两个并开完需要说明的是，我这次是先买了三个并开完，开完后又买了两个并开完 经过分析，可以发现： * 第一天收益极高，接近90%90\%90%，且稳赚不赔，有888 * 第二天收益低，全部亏完 * 第三天收益为0，不亏不赚 * 第四天以一批全赚，且有888 * 第四天第二批亏 * 第五天第一批有赚有亏，有888 * 第五天第二批小赚 于是，我总结出几条规律： 1. 各个结果的概率绝非均等，也没有规律，只与购买批次有关系！\color{red}各个结果的概率绝非均等，也没有规律，只与购买批次有关系！各个结果的概率绝非均等，也没有规律，只与购买批次有关系！ 2. 如果一批中有888，则那一批大概率全赚\color{red}如果一批中有888，则那一批大概率全赚如果一批中有888，则那一批大概率全赚 3. 如果上一批大赚，则这一批会亏或小赚\color{red}如果上一批大赚，则这一批会亏或小赚如果上一批大赚，则这一批会亏或小赚 4. 如果上批亏，则这批收益率为正 5. 收益率若为正，则必大于70%70\%70% 6. 399常伴随888 注：一批是指购买的一批，即只买一个就是单独成批 因此，可以给出建议： 1. 如果一批中有888，那么果断开完\color{red}如果一批中有888，那么果断开完如果一批中有888，那么果断开完 2. 如果上一批大赚，那么这一批少买，来抵消会亏的debuff\color{red}如果上一批大赚，那么这一批少买，来抵消会亏的debuff如果上一批大赚，那么这一批少买，来抵消会亏的debuff 3. 如果上批亏，则这批大胆全买，吃满buff\color{red}如果上批亏，则这批大胆全买，吃满buff如果上批亏，则这批大胆全买，吃满buff 4. 如果连亏两次，就把剩下的留到第二天开\color{red}如果连亏两次，就把剩下的留到第二天开如果连亏两次，就把剩下的留到第二天开 5. 出了888千万别上头，不要有“乘胜追击”的心态\color{red}出了888千万别上头，不要有“乘胜追击”的心态出了888千万别上头，不要有“乘胜追击”的心态 注：我还没有试过一次买五个以上，留到第二天开，因此不要轻易尝试 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY6 今天我分两批买，2+3 第一批199+66，第二批888+399+66，总收益623，收益率63%63\%63% 再次验证了399常伴随888出现 创作不易（成本巨大），留个赞吧，我们一起拿罐头，双赢！\color{purple}创作不易（成本巨大），留个赞吧，我们一起拿罐头，双赢！创作不易（成本巨大），留个赞吧，我们一起拿罐头，双赢！

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

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

【获奖公告】挑战赛#27

【获奖公告】挑战赛#27 用户ID 用户昵称 获奖 4699151 @梦里初晴 拼图X1 +盲盒X1+1500罐头 4480835 @Su0710 拼图X1 +盲盒X1+600罐头 2901632 @༺ཌༀ复仇者.凤凰.浅琪ༀད༻ 拼图X1 +盲盒X1+600罐头 3621376 @🥥 拼图X1 +盲盒X1+600罐头 4244987 @Gragher 拼图X1 +盲盒X1+600罐头 494973 @不会C++的一只屑生姜 拼图X1 +盲盒X1+300罐头 1371791 @复仇者_天之神_银色子弹 拼图X1 +盲盒X1+300罐头 3099184 @༺ཌༀ诺崽的树(互关)ༀད༻ 拼图X1 +盲盒X1+300罐头 4753295 @枫岚 拼图X1 +盲盒X1+300罐头 3640785 @肖越腾 拼图X1 +盲盒X1+300罐头 4784858 @195****3060 拼图X1 +盲盒X1+300罐头 5346770 @Micheal Jordan 拼图X1 +盲盒X1+300罐头 4221310 @༼ つ ◕_◕ ༽つ(ˉ﹃ˉ)‏ 拼图X1 +盲盒X1+300罐头 4997640 @Srobot 拼图X1 +盲盒X1+300罐头 4057292 @沈思邈 拼图X1 +盲盒X1+300罐头 3298235 @yanghongzheng 拼图X1 +盲盒X1+300罐头 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 获奖信息填写 恭喜以上获奖同学🎉 为了避免出现漏发或因未关注AC君而错过寄件信息的情况，请获奖的同学们尽快私信AC君提供收件信息。具体信息包括： 获奖赛事名称： 收件人姓名： 收件手机号码： 收件地址：需详细填写，包括省、市、区、街道及具体住址 请确保提供的信息准确无误，以便我们能够顺利将礼品送达。感谢您的配合！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 前100名违规名单 在本场赛事的审核中，我们对前 100 名选手的代码进行了检测，发现 72 名用户存在疑似 AI 生成或高相似度代码的情况。公平竞赛至关重要，请各位严格遵守规则，维护良好的竞赛环境。 用户ID 用户昵称 3751693 @神-爸爸 5205870 @༺ཌༀ༒AC王者༒ༀད༻ 3614898 @RuiDaShuai2025 4592666 @𝓐𝓘𝓮𝓻 4326899 @狐夏聆哲_Anarilune. 5212050 @༺ཌༀ`§☯༺ཌ༒༺☯§′ༀད༻ 5134294 @黑妞 5320353 @181****9763 5439864 @Eric 3861543 @云雾星海 3431448 @得吃鼠鼠 5085318 @deepseek 4958203 @WA?不存在的 5034831 @一只开挂的蒟蒻 5347557 @we go! 4921199 @wwh 3708542 @徐梓铭 3361566 @12岁巅峰学生（互关） 5396059 @Lucky 5080911 @dvf 4960039 @请输入文本 4578820 @666 4609559 @老杨 4950030 @土豆（灿） 4963362 @我的世界老玩家（互关，专攻难题） 3455548 @十万暴击 3477229 @EasonDai 3809107 @AC 5205437 @里昂熠熠 5205370 @TLE君（自闭中） 4955240 @夏绍智(必回关) 5403433 @栖月 4126504 @༺ཌༀ◎真仙◎ༀད༻ 5433579 @༺ཌༀཉ༒ 砚辞 ༒ༀད༻ 4321981 @Minecraft 3460964 @终极主宰大神（求关注必回） 4790834 @异雷-彩色庆祝版 5431616 @134****0429 5345022 @Phantom_73 2454098 @i闪天天开心 5206173 @Google Chrome 5402041 @liuziang250 5401663 @whistleblower 1362696 @大刚 3249248 @陈羿然 4752030 @SD_xm 4976685 @实验小学乔子航 3644432 @黑皇 5216253 @133****8755 4307593 @Dog 5439994 @xjsmsms 4770844 @宇浩 ~-HAPPY 果 4390455 @𝓔𝓣𝓗𝓐𝓝 4909644 @ 4815042 @明月清风（互关） 3050135 @136****7366 5089157 @DAX-CC 4440554 @Ad-梵高无人识 4937905 @王普驿 5371339 @谈damn 5339471 @6AG3 4966462 @哪吒与敖丙 3745777 @Kevin Durant 4768854 @血战狂龙——血虐修罗之骜の流星尾 5194566 @周豫才 5415015 @chf 768428 @AC考试王乾瑄 4938384 @195****3768 4958204 @穷涂墨鹿、 违规与处罚机制（挑战赛 & 巅峰赛） * 第 1–3 次违规： 内部记录，不扣表现分，取消礼品赠送； * 第 4 次违规： 视情况扣除表现分，并取消对应勋章； * 第 5 次及以后违规： 持续扣除表现分。 申诉机制 请在2月8日前👉 提交申诉（需提供详细解题思路）。经审核确认无违规，将撤销本次记录。如果提交申诉后，依旧被判为违规，则禁言7天以示警告。 本轮赛事审核 ：@Gragher，@cjdst 📎 ACGO 官方赛事公平审核规则 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 违规名单累计 * 累计违规 >3 次的用户，统一 禁言 30 天 并扣除ACGO竞赛分； * 累计违规 =3 次的用户，统一 禁言 30 天； * 仅违规 1 次者不予展示。 用户ID 用户昵称 累计历史违规次数 4963362 @我的世界老玩家（互关，专攻难题） 9 3751693 @神-爸爸 8 3455548 @十万暴击 8 4592666 @𝓐𝓘𝓮𝓻 6 3361566 @12岁巅峰学生（互关） 5 4440554 @Ad-梵高无人识 4 4955240 @夏绍智(必回关) 4 4326899 @狐夏聆哲_Anarilune. 3 5206173 @Google Chrome 3 4950030 @土豆（灿） 3 4126504 @༺ཌༀ◎真仙◎ༀད༻ 3

一个新的寻找二次函数顶点的方法？

首先，形如 ax2+bx+cax^2+bx+c ax2+bx+c 的柿子 要变为 k(x−l)2+r (k,l,r不含x)k(x-l)^2+r\ (k,l,r不含x) k(x−l)2+r (k,l,r不含x) 先化简原式 k(x−l)2+rk(x-l)^2+r k(x−l)2+r =k(x2+l2−2xl)+r=k(x^2+l^2-2xl)+r =k(x2+l2−2xl)+r =kx2+kl2−2kxl+r=kx^2+kl^2-2kxl+r =kx2+kl2−2kxl+r 那么你就会发现 (因为 (k,l,r不含x)(k,l,r不含x)(k,l,r不含x) ) {k=abx=−2kxlkl2+r=c\left\{\begin{matrix}k=a \\bx=-2kxl \\kl^2+r=c \end{matrix}\right.⎩⎨⎧ k=abx=−2kxlkl2+r=c 若 x=0x=0x=0 ，则 y=cy=cy=c 嗯对。。。 否则 {k=ab=−2klkl2+r=c\left\{\begin{matrix} k=a \\ b=-2kl \\kl^2+r=c \end{matrix}\right.⎩⎨⎧ k=ab=−2klkl2+r=c 将 k=ak=ak=a 代入方程组 {b=−2alal2+r=c\left\{\begin{matrix}b=-2al \\al^2+r=c \end{matrix}\right. {b=−2alal2+r=c 单独求解①式，得： l=−b2al=-\frac{b}{2a} l=−2ab 将其带入②式 a×b24a2+r=ca\times \frac{b^2}{4a^2}+r=c a×4a2b2 +r=c b24a+r=c\frac{b^2}{4a}+r=c 4ab2 +r=c 所以 r=c−b24ar=c-\frac{b^2}{4a} r=c−4ab2 所以 {k=al=−b2ar=c−b24a\left\{\begin{matrix}k=a \\l=-\frac{b}{2a} \\r=c-\frac{b^2}{4a} \end{matrix}\right. ⎩⎨⎧ k=al=−2ab r=c−4ab2

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

同步发布于 我的 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，直接套用上面的公式求解即可。

官方题解 | 挑战赛#27

挑战赛27题解 本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目标题 难度 T1 午枫的矩形 入门 T2 午枫的字符串移动2 入门 T3 午枫打砖块 普及/提高- T4 午枫的子序列之和 普及/提高- T5 午枫的星星树 普及- T6 午枫的数字华容道 普及/提高- T1 午枫的矩形 题目大意 给定一个矩阵，判断这个矩阵的任意子矩阵是否满足 左上角的数+右下角的数≤左下角的数+右上角的数左上角的数+右下角的数\leq 左下角的数+右上角的数左上角的数+右下角的数≤左下角的数+右上角的数 。 解题思路 由于数据范围只有 1≤n,m≤501\leq n,m\leq 501≤n,m≤50 ，所有直接四层循环嵌套枚举左上角和右下角，同时也能知道左下角和右上角的坐标，直接计算判断即可。 参考代码 T2 午枫的字符串移动2 题目大意 给定一个字符串，可以进行左移和右移的操作任意次，找到所有可以得到的字符串中字典序最小以及最大的字符串。 解题思路 因为可以操作任意次，所以只要单独往一个方向不断移动并且更新字典序最小和最大的字符串即可。 这里可以直接使用 string 类型进行移动的操作，并且也可以使用 min 和 max 函数进行比较字典序大小。 参考答案 T3 午枫打砖块 题目大意 给定 nnn 行砖块，每行向右无限延伸并且有且有一段连续的区间为奖励砖，每次可以选择一个区间长度 ddd ，并且将这 ddd 列每行所有的砖块都破坏，奖励砖只要被破坏一个格子就会被全部破坏，求将所有奖励砖都破坏需要的最少操作次数。 解题思路 这是一道经典的贪心问题，在排序时我们会想到，如果破坏一个奖励砖的最右端，那么就会破坏更多的奖励砖，所以我们按照右端点排序，模拟每次打破当前剩余第一个奖励砖的最右端即可。 参考答案 T4 午枫的子序列之和 题目大意 给定一个长度为 nnn 的数组和一个整数 kkk ，求数组 aaa 的所有连续子序列中，元素之和等于 kkk 的个数。 解题思路 首先我们可以预处理前缀和数组 sss ，即需要求区间满足 sr−sl−1=ks_r-s_{l-1}=ksr −sl−1 =k 的区间个数。问题就转化成了非常经典的问题。 枚举区间右端点 rrr ，同时统计已枚举前缀每个 sls_lsl 的个数，那么对于这个 rrr ，对答案贡献为满足 sl−1=sr−ks_{l-1} = s_r - ksl−1 =sr −k 的所有 lll 的个数。那么问题又进一步简化为：统计 si=xs_i = xsi =x 的个数。注意到数据范围无法用桶数组直接记录元素个数，考虑使用离散化或 map 直接统计都可完成。 参考代码 方法一：map 方法二：离散化 T5 午枫的星星树 题目大意 给定一棵树，问是否存在一个点与其他所有点直接相连。 解题思路 记录所有点的度数，判断是否存在一个点的度数为 n−1n-1n−1 即可。 参考代码 T6 午枫的数字华容道 题目大意 有 999 个点 mmm 条边的无向图，其中有 888 个数字放置在不同点上，有一个没有数字的点，可以通过移动将数字移动到相邻没有数字的点上，求最终将数字 1∼81\sim 81∼8 分别放在顶点 1∼81\sim 81∼8 上的最少操作次数。 解题思路 我们可以将 999 个顶点上所存放的数字用字符串表示状态，例如 254806137 表示顶点 111 存放数字 222 ，顶点 222 存放数字 555 ，依此类推，特殊地，数字 000 表示该点为空。那么终点就可以用 123456780 表示。 由于每次移动都会从一种状态变为另一种状态，我们不妨将每种状态看作一个结点，那么所有状态以及状态与状态之间的变换就可以形成一张无向图，于是我们只需要在图上用 bfsbfsbfs 跑最短路即可。由于结点是以字符串表示的，所以可以使用 map 存储从起点状态到达所有状态结点的最短路径长度。 参考代码

数状数组/线段树 代码存档

UPDATE: 决定把这个做成较为详细的笔记 UPDATE: 骗你的，做不下去了，只做了树状数组 排版很乱，见谅哈。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1.树状数组（BINARY INDEXED TREE,BIT,二叉索引树） 简介：可以处理区间修改，查询区间和/差等问题（仅支持前缀可减的操作）。 问题：给出一个数组 {an}\{a_n\}{an }，请在 log⁡n\log{n}logn 的时间复杂度内执行区间修改或区间查询操作。 关于树状数组，我们从一个很聪明的函数讲起： lowbit(x)=x&(−x)\tt{lowbit(x)=x\&(-x)}lowbit(x)=x&(−x) 指 xxx 与 −x-x−x 按位与的结果。 可以发现，当 xxx 是奇数时，lowbit(x)=1\tt{lowbit(x)=1}lowbit(x)=1，反之 lowbit(x)=\tt{lowbit(x)}=lowbit(x)= 二进制下的 xxx 从左往右出现的最后一个 111 及其后面的 000 组成的数的十进制。这么听着有点绕，例如 lowbit(6)\tt{lowbit(6)}lowbit(6)，(6)10=(110)2,(6)_{10}=(110)_2,(6)10 =(110)2 , 取 101010，得 (10)2=2(10)_2=2(10)2 =2，所以 lowbit(6)=2\tt{lowbit(6)=2}lowbit(6)=2。当然这个只是铺垫后面的内容，听不懂也没关系。你只需要知道 lowbit(x)\tt{lowbit(x)}lowbit(x) 的值一定是 222 的幂次，前提 x≠0x\ne 0x=0。 关键在于我们按 lowbit(x)\tt{lowbit(x)}lowbit(x) 的值将每个数分层并连边，居然神奇的出现了一棵二叉树！（如下图） 这棵二叉树非常神奇，对于节点 iii，如果他是左子结点，他的父节点为 i+lowbit(i)\tt{i+lowbit(i)}i+lowbit(i)，否则他的父节点为 i−lowbit(i)\tt{i-lowbit(i)}i−lowbit(i)。因此我们可以利用 lowbit\tt{lowbit}lowbit，对区间段进行前缀和计算。 构造一个辅助数组 c[]c[]c[]，定义 cic_ici 为覆盖节点 iii 及其左子树的区间和，即： ci=∑i−lowbit(i)+1iaic_i=\sum_{i-lowbit(i)+1}^i a_i ci =i−lowbit(i)+1∑i ai 这时我们回归问题。 修改 观察 cic_ici 的定义，修改一个节点的值，只需要同步修改在其右上方的祖先的值即可。 查询 只需要将所有其左上方的祖先及其本身的值即可。 对于区间修改问题，由于 query\tt{query}query 本质上是前缀和，所以差分一下即可（换句话说，区间修改问题必须有可差分性） 模板题，上模板。 例题： * 股票 提醒各位初学者，本题虽然不必离散化，但是你拿 aia_iai 建的树状数组就需要注意阈值上限是 max⁡ai\max a_imaxai 不是 nnn 了。可能你们会觉得这句话很糖。 * 逆序对 由于 aia_iai 达到了 10910^9109，我们无法直接按照 aia_iai 的值建树状数组，因此考虑离散化： * 1.复制 aaa 数组存入 ttt，将 ttt 排序。 * 2.将 ttt 用 unique\tt{unique}unique 函数去重。 * 3.用二分找原 aia_iai 在 ttt 中的位置。 这样我们就得到了 aia_iai 的相对大小顺序，把值域缩到了 5×1055\times 10^55×105 之内，可以建树状数组了。 2.线段树/(LAZY_TAG) 没写完。 3.权值线段树 洛谷我没找到板（没有给权值线段树の标签），自己放一个草题。 题目描述 给出 n,{an}n,\{a_n\}n,{an }，约定 b1=a1b_1=a_1b1 =a1 。对于 2≤i≤n2\le i \le n2≤i≤n： bi=min⁡j=1i−1∣aj−ai∣ b_i=\min_{j=1}^{i-1}|a_j-a_i| bi =j=1mini−1 ∣aj −ai ∣ 求出 {bn}\{b_n\}{bn }。 输入 给出 n,{an}n,\{a_n\}n,{an } 输出 {bn}\{b_n\}{bn } 输入 111 输出 111 1≤n≤105,1≤ai≤1071\le n \le 10^5,1\le a_i\le 10^71≤n≤105,1≤ai ≤107 无需离散化&动态开点 Code:\tt{Code:}Code: 回转寿司,luogu5459,绿 九转大肠有没有食欲 发现与区间和有关，套上前缀和 sumsumsum。 考虑列不等式 L≤sumr−suml−1≤RL\le sum_r-sum_{l-1}\le RL≤sumr −suml−1 ≤R，直接维护这个是 n2n^2n2 的肯定不现实。 考虑变换得 sumr−R≤suml−1≤sumr−L(l<i)sum_r-R\le sum_l-1\le sum_r-L(l<i)sumr −R≤suml −1≤sumr −L(l<i)，考虑枚举 sumisum_isumi ，那么我们只要找出满足条件的 suml−1sum_{l-1}suml−1 的数量，就是对于 sumisum_isumi 的选择。 于是我们使用权值线段树维护 sumsumsum 的值，也就是要计算的 [sumi−R,sumi−L][sum_i-R,sum_i-L][sumi −R,sumi −L]，那把小于 iii 的 sumjsum_jsumj 全部丢进权值线段树即可。 需要注意的是，本题阈值很大，记得动态开点处理。

AC罐头商店使用说明

AC罐头商店 使用说明 💰 一、罐头获取方式 刷题赚罐头 🎯 获取方式 罐头奖励 说明 攻克新题 1-7罐头/题 每成功攻克一道自己未AC的官方题目，根据题目难度获得罐头：• 入门：1罐头；• 普及-：2罐头；普及/提高-：3罐头；• 普及+/提高：4罐头；• 提高+/省选：5罐头；• NOI/CTSC级别：7罐头；每日上限：5题（即每日最多通过5道新题获得罐头） 题目首杀 5-35罐头/题 首位攻破“零通过”的官方题目，根据题目难度获得• 入门：5罐头；• 普及-：10罐头；• 普及/提高-：15罐头• 普及+/提高：20罐；• 提高+/省选：25罐头；• NOI/CTSC级别：35罐头 ；每日上限：5题（即每日最多通过5道首杀获得罐头） 首次竞赛报名 20罐头 用户第一次报名ACGO的官方竞赛时获得 排位等级晋升 100-800罐头/级 排位等级从上一级晋升到下一级时获得（每个等级仅奖励一次）：• 青铜→白银：100罐头；• 白银→黄金：200罐头；• 黄金→铂金：300罐头；• 铂金→钻石：400罐头；• 钻石→大师：600罐头；• 大师→王者：800罐头 天梯闯关过关 1-200罐头/关 每通过一关天梯闯关即可获得罐头，奖励金额随关卡难度递增，具体以关卡实际显示为准 活跃赚罐头 🎪 获取方式 罐头奖励 每日上限 每日点赞 1罐头/次 5次（5罐头） 每日评论 1罐头/次 5次（5罐头） 每日收藏题单 1罐头/次 5次（5罐头） 帖子被点赞 1罐头/次 10次（10罐头） 题单被收藏 5罐头/次 10次（50罐头） 每日活跃罐头上限：75罐头（5+5+5+10+50） 运营与贡献 🏆 获取方式 罐头奖励 说明 管理员手动发放 50-5000罐头 适用于以下场景：• 参与各类赛事并按赛事规则分配奖励；• 贡献优质题解、技术分享等内容被官方采纳；• 为社区发展提供特殊贡献等 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⏰ 二、罐头过期说明 滚动过期规则 AC罐头采用 【滚动过期】 方式管理： 1. 过期时间：每个自然年年底（12月31日23:59） 2. 过期范围：上一个年度获得且未消耗的罐头 3. 过期示例： * 2024年获得的罐头，将在2025年12月31日23:59过期 * 2025年获得的罐头，将在2026年12月31日23:59过期 * 以此类推... 过期提醒服务 * 提醒时间：每年12月1日开始 * 提醒方式： * 站内信通知 * 平台置顶帖子公告 * 提醒内容：“您有XXX罐头即将在12月31日到期，请尽快兑换！” 过期应对策略 1. 及时消费：不要过度囤积罐头，看到心仪商品及时兑换 2. 年度规划：每年11月开始规划罐头使用，避免年底过期浪费 3. 关注提醒：每年12月注意查看站内信和公告 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💡 三、重要提醒 1. 罐头与账号绑定，不可转让、不可交易 2. 商品一经使用，概不退换，请确认后再购买 3. 请合理安排罐头使用计划，避免过期造成浪费 每年年底记得清空旧罐头，迎接新一年的赚罐头之旅！ 🎉

非官方题解 | 嘻哈赛#1题解

WOC榜10了，感谢各位大佬观看，点赞的全家健康，长命百岁，比赛次次都AK 出了商城功能以后，凡是在我这个帖子里随便发几条评论、点个赞都能拿罐头！ 求官方批准@AC君 求点赞 点个赞吧 求你了求你了求你了求你了求你了求你了求你了求你了求你了 狗友们真是太6了！ 一起冲破榜一 回归正题： 非官方题解 | 嘻哈赛#1题解(C++&PYTHON) 赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目名称 题目难度 T1 可爱表情 入门 T2 自我介绍 入门 T3 生日祝福 入门 T4 比价格 入门 T1 可爱表情 题目大意： 直接输出5行表情： 解题思路： c++版： 直接用cout输出并换行 python版： 直接用print输出并换行 参考代码 c++版： python版： T2 自我介绍 题目大意： 直接输出3行自我介绍的内容： 解题思路： c++版： 直接用cout输出并换行 python版： 直接用print输出并换行 参考代码 c++版： python版： T3 生日祝福 题目大意： 按照以下固定格式： 注意：标点符号要使用中文标点 解题思路： c++版： 首先定义一个字符串用string和cin输入，在把祝福语和变量连接起来用cout一起输出 python版： 首先input()函数进行输入一个变量，在用printd的固定格式输出(如f格式化输出.....) 注意：标点符号要使用中文标点!!! 参考代码： c++版： python版： T4 比价格 题目大意： 同一本书，比较两家书店的价格，从中找出价格最低的输出那个价格 解题思路： c++版： 首先定义两个整数用int和cin输入，在用cout输出min比较两个数谁大谁小大结果 python版： 首先input()函数进行输入两个整数，在用print输出min比较两个数谁大谁小大结果 参考代码： python版： 团队传送门（你敢不敢加入此团队？） 如果要团队合作，请私信。

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

特爱写日记。 其实我本来就想写的，然后看见了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 57.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。