预防团贩子(一人观看，一人受益)

拍照留念: 最近也是看到好多的团被毁，所以就发了这个帖子 预热帖子:见鬼了、见鬼了（讲事&交朋友）、@盛大666你有、、啊、《傻福玩意儿之盛大666》、团贩子删团(疑似一路走好卷土重来 这些都是最近被毁的团的帖子，今天给大家讲一下如何避免团贩子删团 一、如何甄别团贩子 团贩子，顾名思义就是对团队造成破坏的人，这个我相信大家都理解 团贩子会利用自己的权限来把团队内的人踢除，或对团队造成别的损失 团贩子会尝试去向队长或其他拥有角色设置权限的人要权限，当获得权限后就会开始放肆起来 如果谁没有给到他权限，团贩子就会想尽各种办法骗到权限 大家可以想一想，一个普通成员肯定不会随便要权限吧 二、如何防范团贩子 其实最简单的方法就是不要乱给他人权限，除非是受信任用户 1. 在团队的"成员"选项中找到"角色管理" 2. 在"角色管理"中找到角色的"设置权限"，点进去 3. 如果是普通用户就像这样设置就行了，受信任用户可以加上"添加成员"和"邀请成员"之类的选项，总之就是不要加上"移出成员"这个选项，"移出成员"就是踢出团队的意思，就是开头所说的团贩子最需要的权限 三、举报团贩子相关 如果遭遇了团贩子删团之类的情况，请不要再发帖了！ 因为AC君已经发过帖了，里面有明确地教程如何避免团贩子。如果遇到团贩子删团类似的情况，属于是队长和其他管理员的失职，举报后很容易无果，而且还容易被喷 不是团贩子非常嚣张的情况下，AC君是不会给予处理的 一路走好曾经是猖狂到名字改成了"AC君你有本事封我号啊"这个地步，所以AC君才会处理的 参考帖:【团队安全运营公告】重要提醒，这个是AC君发的帖子 请大家在下方评论或点赞，把此帖顶上去 一人观看，一人受益

互动｜未来实物周边大征集

AC狗友们！🙌 社区的罐头商城上线有一阵子了，不知道大家逛得怎么样？之前上架的几款实物周边，手速快的小伙伴是不是已经抱回家了？👀 💡 第一件事：未来实物周边大征集！听劝！ 我们非常想知道大家真正喜欢什么！你希望ACGO出什么样的实物周边？ 无论是实用派还是收藏党，或者更大胆的想法，都欢迎在评论区大声说出来！你的建议，很有可能成为下一批上架的实物哦！ 别客气，尽情畅想吧～ 🎉 第二件事：商城上新啦！三款全新实物闪亮登场！ 这次带来的三款周边，每一个都是“AC”路上的好伙伴，希望能给你的编程日常加点料。快来看看有没有戳中你的： 1️⃣ C++钥匙扣（牛油果绿定制钥匙扣） 👉 https://www.acgo.cn/mall/product/145 2️⃣ ACGO笔记本（原创设计厚本子） 👉 https://www.acgo.cn/mall/product/144 3️⃣ ACGO鼠标垫（自研AC鼠标垫） 👉 https://www.acgo.cn/mall/product/143 🎁 互动有奖：点赞 TOP5送 昵称变色卡！ 只要在评论区留言，告诉我们你想要的周边建议，我们就会选出点赞数最高**的5位小伙伴，每人送出昵称变色卡 作为奖励！💪 * 活动时间：即日起至 3月20日 * 开奖方式：活动截止后，将在本帖公布获奖名单，并通过发放罐头奖励。 心动不如行动，快来评论区留下你的奇思妙想吧！也别忘了去商城逛逛，把心仪的宝贝带回家～ > 往期互动话题

CXXP类似赛宣传

半个#2模拟赛！不是官方出题！ 参加竞赛 （邀请码：dtRh）CXXP类似赛|非官方 出题进度 * T4（最后一题）已经出完，并且AC * T1整完了，AC，T2出现重点问题，已经改了15次awa * 所有题目全部出完，等着周五作答看好戏awa * 下调T2，T3难度，上调T4难度，更改部分题目测试点 * 检查题目，修改部分测试点 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 广告： 欢迎加入CXXP公开赛出题组，要求点此处，有意愿且符合要求的私信忘川秋库。 申请加入写c++还是吃皮皮虾团队 天启千答 OJ 申请加入天启空间 相关贴子 题解 赛后总结贴 赛前宣传贴及参加比赛 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 突然意识到竞赛，没有验题人AWA 榜八吗，有点意思 招募一个验题人，要求是拿过奖（认证过的），如果没有也没关系AWA

为啥错了！

原题链接：A1.A+B problem

【获奖公告】巅峰赛#31

【获奖公告】巅峰赛#31 名次 用户ID 用户昵称 奖励 1 4221310 @༼ つ ◕_◕ ༽つ(ˉ﹃ˉ)‮ 随机拼图X1 +盲盒X1+2000罐头 2 494973 @不会C++的一只屑生姜 随机拼图X1 +盲盒X1+800罐头 3 5347557 @TQjc 随机拼图X1 +盲盒X1+800罐头 4 5371362 @5371362 随机拼图 × 1+盲盒X1+500罐头 5 4609559 @老杨 随机拼图 × 1+盲盒X1+500罐头 6 3621376 @🥥 随机拼图 × 1+盲盒X1+500罐头 7 1590033 @cjdst 随机拼图 × 1+盲盒X1+500罐头 8 4744648 @Lost 随机拼图 × 1+盲盒X1+500罐头 9 4784858 @NULL 随机拼图 × 1+盲盒X1+500罐头 10 5063512 @daitingyu 随机拼图 × 1+盲盒X1+500罐头 11 1371791 @复仇者_天之神_银色子弹 随机拼图 × 1+盲盒X1 +200罐头 12 4997640 @Srobot 随机拼图 × 1+盲盒X1 +200罐头 13 4181234 @你是不是喜欢c++ 随机拼图 × 1+盲盒X1 +200罐头 14 1804874 @AKIOI 随机拼图 × 1+盲盒X1 +200罐头 15 4497779 @呃の 随机拼图 × 1+盲盒X1 +200罐头 16 5246373 @‮🐱‍🚀 随机拼图 × 1+盲盒X1 +200罐头 17 3871431 @许睿xu rui 随机拼图 × 1+盲盒X1 +200罐头 18 4816307 @TLE君 随机拼图 × 1+盲盒X1 +200罐头 19 4399421 @异小号 随机拼图 × 1+盲盒X1 +200罐头 20 4057292 @FanBoys 随机拼图 × 1+盲盒X1 +200罐头 21 4193026 @皮皮虾_复仇者_钧 100罐头 22 4174170 @山衔落日——乘风破浪 100罐头 24 4533948 @Khalil 100罐头 25 4683247 @𝓘𝓭𝓬𝓳_𝓎𝓈𝓈✔ 100罐头 26 955476 @潇洒地走 100罐头 27 4412829 @假伪人 100罐头 28 5471887 @yuchaneko 100罐头 30 2454098 @i闪天天开心 100罐头 31 2853133 @初识c++ 100罐头 32 3298235 @yanghongzheng 100罐头 复核成功 名次 用户ID 奖励 3622268 @欢迎收看第26季《空中浩劫》 随机拼图 × 1+盲盒X1 +200罐头 4337775 @芙宁娜·德·枫丹 100罐头 1763578 @很烫的凉水 100罐头 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 获奖信息填写 恭喜以上获奖同学🎉 为了避免出现漏发或因未关注AC君而错过寄件信息的情况，请获奖的同学们尽快私信AC君提供收件信息。具体信息包括： 获奖赛事名称： 收件人姓名： 收件手机号码： 收件地址：需详细填写，包括省、市、区、街道及具体住址 请确保提供的信息准确无误，以便我们能够顺利将礼品送达。感谢您的配合！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 前100名违规名单 在本场赛事的审核中，我们对前 100 名选手的代码进行了检测，发现 67 名用户存在违规或疑似AI生成或高相似度代码的情况。公平竞赛至关重要，请各位严格遵守规则，维护良好的竞赛环境。 违规与处罚机制（挑战赛 & 巅峰赛） * 第 1–3 次违规： 内部记录，不扣表现分，取消礼品赠送； * 第 4 次违规： 视情况扣除表现分，并取消对应勋章； * 第 5 次及以后违规： 持续扣除表现分。 申诉机制 请在3月15日前👉 提交申诉（需提供详细解题思路）。经审核确认无违规，将撤销本次记录。如果提交申诉后，依旧被判为违规，则禁言7天以示警告。 本轮赛事审核 ：@Gragher，@cjdst，@不会C++的noah，@Zzzzzzsr（不处） 📎 ACGO 官方赛事公平审核规则 用户ID 用户昵称 4976685 @消失的AC 无尽的RE 5067951 @158****5686 5415376 @132****7810 5075823 @Administrator 4960039 @请输入文本 4592666 @人间客 · 云舒 5085318 @deepseek 5445480 @复仇者 开心就好 3751693 @神-爸爸 4252088 @无敌的鳖佬仔给老爷爷猜猜被 4455678 @徐书睿 3428706 @潘宸菲 3030196 @姚梓宸 4186361 @199****0937 3506467 @神兽•CHINA💤 3330783 @箜 3971643 @wcqk 5345022 @Phantom_73 4883557 @世界终予你好 3957035 @陈桐旭acgo.cn 2989085 @Sky-飞雪🍞 4671448 @༺ཌༀ🤖ༀད༻ 2268581 @丛文熹 2182324 @zjr 2872425 @18岁打WA少年不会梦到AC学姐 3482800 @漫步星云 4542117 @156****0405 4235962 @🎈🎈🎈🎈🎈🎈🎈🎈 3943744 @water 4976800 @哪吒之魔童降世 5187838 @谷锦源 2325669 @152****0793 774357 @🕈.👎.☝✌💧❄☜☼ 2795259 @Allen 3644432 @黑皇 3580701 @༺༒༻C++菜鸟༺༒༻ 5205556 @黄羽飞 5441203 @实力不详 4209222 @ÆÆÆÆÆÆÆ 4816377 @Zorange(ZC) 4259470 @Eucatastrophe‌ 4321981 @MINECRAFT 765860 @毛 5408433 @一颗可爱的冰西瓜 3809107 @AC 3172520 @猫七夜 1730571 @Dragon 3798360 @nightmare 4739854 @一架正在起飞的华航B747 4548538 @死灵圣法神 4849533 @153****3649 3964108 @ACGO 3803163 @cys 3483842 @Jason-JHT 5335472 @善 3942689 @‮ 5463470 @主教.蓝慈 4173007 @f u c k ccf 5205540 @杨彦驰(Kards入) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 违规名单累计 * 累计违规 >3 次的用户，统一 禁言 30 天 并扣除ACGO竞赛分； * 累计违规 =3 次的用户，统一 禁言 30 天； * 仅违规 1 次者不予展示。 用户ID 用户昵称 3751693 @神-爸爸 4592666 @人间客 · 云舒 4252088 @无敌的鳖佬仔给老爷爷猜猜被 3580701 @༺༒༻C++菜鸟༺༒༻ 4976685 @消失的AC 无尽的RE 2795259 @Allen 5345022 @Phantom_73 5187838 @谷锦源 765860 @毛 4960039 @请输入文本 5445480 @复仇者 开心就好 3971643 @wcqk 4337775 @芙宁娜·德·枫丹 774357 @🕈.👎.☝✌💧❄☜☼ 3644432 @黑皇 5205556 @黄羽飞 4321981 @MINECRAFT 1730571 @Dragon 4548538 @死灵圣法神

为什么错了？

我已经做出来了哈：https://www.acgo.cn/discuss/study/73822 这能上榜大家多给点赞，刷罐头\color{yellow}{这能上榜大家多给点赞，刷罐头}这能上榜大家多给点赞，刷罐头 我不懂错在哪：

官方题解 | 巅峰赛31

巅峰赛31题解 本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目标题 难度 T1 雾港城的神秘区域 入门 T2 雾港城的符文 普及 - T3 雾港学宫的括号匹配 普及/提高- T4 雾港实验室的高压服务器 普及/提高- T5 雾港冲刺营的队伍序列 普及+/提高 T6 雾港实验室的神秘联通块 普及+/提高 T1 简要题解 关键只看信标数 k：删一条边会让连通块数量从 1 变成 2，再删一条变成 3，总之删 x 条边就会得到 x+1 个连通块。要求每块信标数 ≤1，若有 k 个信标，就至少需要 k 个连通块来“装下”它们，所以必须有 x+1≥k，也就是 x≥k−1；另一方面总能做到 k−1：把所有信标连起来的最小连通子树里，信标一定出现在叶子上，反复把一个叶子信标与子树内部相连的那条边切断，就能一次分离出一个只含 1 个信标的连通块，做 k−1 次即可把所有信标分到不同块里。于是答案就是 max(0, k−1)。 参考代码 T2 简要题解 任何长度 ≥4 的回文子串内部一定会包含一个长度为 2 的回文（相邻相等）或者长度为 3 的回文（形如 aba），所以只要把长度 2 和 3 的回文都挡住，就不会出现更长的回文。于是从左到右贪心构造保留下来的串 t：依次尝试把当前字符加到 t 末尾，如果会造成 t 的最后两位相等，或最后三位形成回文，就删掉这个字符；否则保留。这样每次只在“当前字符一加就必然违规”的情况下才删除，而且违规只可能由最新加入的字符触发，因此这个贪心的删除次数就是最少的，整体 O(n)。 参考代码 T3 简要题解 从左到右扫描字符串，用 bal 记录当前还没被匹配的左括号数量。遇到 '(' 就 bal++；遇到 ')' 时如果 bal>0 说明能和之前某个 '(' 配对，就 bal--，否则这个 ')' 无论如何都配不到，只能删除，答案加一。扫描结束后 bal 还剩多少，表示有多少个 '(' 没法被匹配，只能删掉它们，所以答案再加上 bal。 参考代码 T4 简要题解 迁移发生在什么时候其实不重要：如果某个任务打算在区间中间才迁走，把它改成在 l_i 一开始就迁走只会让 A 的压力更小，不会变大，所以等价于“直接选出至多 K 个区间整段不留在 A 上”。于是问题变成删掉至多 K 个区间，让剩余区间的最大重叠数最小。我们二分答案 X，判定是否能把最大重叠压到 ≤X：按 l 从小到大扫一遍，用 multiset 维护当前还没结束的右端点集合（右端点 < 当前 l 的就删掉），每插入一个新区间后如果集合大小变成 X+1，说明此时必须删掉一个区间才能不超限，贪心删右端点最大的那个（它拖得最久，最容易影响后面），统计最少删掉的数量是否 ≤K。二分最小可行的 X 即答案。 参考代码 T5 简要题解 要让名次尽量小，只需要让自己的最终昵称字典序尽量小，因为当昵称变得更小的时候，队伍里“小于等于它”的人数只会减少，不可能增加，所以名次是单调变好的。于是从左到右处理自己的字符串，高位比低位重要：只要还能动手并且预算够把当前位置至少降低 1 位，就应该立刻动这个位置，否则再怎么改后面都无法在字典序上超过“把更靠左的位置变小”。并且一旦决定改某个位置，为了让字典序尽可能小，当然应当在不超过预算的前提下把它尽量降到更小（同一位置降得更小不会额外消耗动手次数）。因此对每个位置 i 计算最多能降低的位数 delta=min(S[i]-'a', B/p_i)，若 delta>0 就把字符减去 delta、扣除 delta*p_i，并把可修改位置数 K 减 1。得到最终昵称 T 后，将其他人的昵称排序，用 upper_bound(T) 统计有多少昵称字典序小于等于 T（同名也算在前面，因为你报名最晚），名次就是这个数量加 1。 参考代码 T6 简要题解 把每条询问的答案看成在 [1,m][1,m][1,m] 上的一个“最早满足”的位置。连通性具有单调性：若在时刻 ttt 已经连通，那么在任意 t′>tt'>tt′>t 也一定连通，因此每个询问都可以二分答案。为了避免对每个询问都单独重建并查集，把所有询问的二分过程并行起来：每一轮对仍未确定的询问取中点 midmidmid 分桶，然后按 midmidmid 从小到大推进时间指针，依次把前 midmidmid 条边用并查集合并，在对应桶里判断这些询问是否连通，从而收缩各自的二分区间。重复约 log⁡m\log mlogm 轮后区间收敛得到最早连通时刻；若收敛到 m+1m+1m+1 则表示直到最后也不连通输出 −1-1−1，另外 u=vu=vu=v 的询问直接输出 000。 参考代码

KTXY Round 1 赛后总结帖

本帖为 KTXY Round 1 赛后总结帖。 感谢各位参加本次比赛。 赛后总结 (未排除作弊) 本次比赛 202020 人有分。 题目 通过率 预期 AAA 50%50\%50% 符合预期 BBB 0%0\%0% 低于预期 CCC 0%0\%0% 略低于预期 DDD 0%0\%0% 符合预期 获奖名单 由于只有 A 题有通过，故剩余题目的首 A 奖将分配给前十名。 首 A 奖 @lkh1009（充电勿扰） 获得 120120120 罐头。 排名奖 @leo120306 @你是不是喜欢c++ @不会C++的一只屑生姜 @不会C++的noah @lkh1009（充电勿扰） 分别获得 888,200,200,200,200888,200,200,200,200888,200,200,200,200 罐头。 奖池剩余 @leo120306 @你是不是喜欢c++ @不会C++的一只屑生姜 @不会C++的noah @lkh1009（充电勿扰）@终极主宰大神（求关注必回）@Zzzzzzsr（不处） @星海 @编程之神 @CuSn 均获得 108108108 罐头。 题外话 初步评定难度为绿蓝紫紫，可以将自己的想法发表在评论区。 题解

#创作计划#个性线段树模版

本篇只讲简单的线段树，仅建树、求区间最大/最小值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 其他大佬的模版都比较长，不易理解，读起来也比较费劲，今天分享一款比较简短的蒟蒻式模版 废话不多说，有点二叉树基础的狗友都知道： （仅节点编码） 那么我们的模版也会根据这个小知识点进行扩张 1.建树 这就是建树，其中思路与归并排序类似，递归从根节点开始分别向其左子树与其右子树遍历建树 tree[i]tree[i]tree[i]表示节点编号为iii的线段树节点的存值 橙色为原数组区间，红色为节点存值，黑色为节点编号。 本图以最大值建树为例 即节点存的值是其左子树与右子树中的最大值 举个栗子：节点1存的就是区间[1,2][1,2][1,2]与区间[3,4][3,4][3,4]合并所得的最大值 模拟过程 1.递归区间[1,4][1,4][1,4] 条件不成立，递归结果max([1,2],[3,4])max([1,2],[3,4])max([1,2],[3,4]) 2.递归区间[1,2][1,2][1,2] 条件不成立，递归结果max([1,1],[2,2])max([1,1],[2,2])max([1,1],[2,2]) 3.两个子区间条件成立，回溯至2 4.结果为[2,2][2,2][2,2]，回溯至1 5.递归区间[3,4][3,4][3,4] 条件不成立，递归结果max([3,3],[4,4])max([3,3],[4,4])max([3,3],[4,4]) 6.两个子区间条件成立，回溯至5 7.结果为[4,4][4,4][4,4]，回溯至1 8.结果为[1,2][1,2][1,2]，递归结束，建树成功 好了，咱们已经获得了一棵优美的维护最大值的线段树了，接下来就是查询了 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2.查询

#创作计划# 矩阵快速幂

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 前言 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 好久没有发帖子了，今天写个创作计划吧。 各位大佬嘴下留情，不喜轻喷，欢迎提建议！ 本文将用通俗易懂的方法讲懂矩阵快速幂 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 铺垫 （若你已经知道且学会快速幂和矩阵乘法，可以直接跳到正文部分） 一、快速幂 先来复习一下快速幂。 以上是一个简单的快速幂模板。（如果到这里你没有看懂，请重学快速幂） 二、矩阵 矩阵，相当于 c++ 中的二维数组，是一个整齐排列的“数字表格”，举个例子： [1,14,51,4]\begin{bmatrix} 1,1\\ 4,5 \\ 1,4 \end{bmatrix} 1,14,51,4 这就是一个矩阵，它是一个 333 行 222 列的矩阵。（到这里都应该很好理解吧） 三、矩阵的运算 两个矩阵之间支持多种运算，今天我主要讲解加、减、乘法运算。 1、加减运算 加减运算的前提是两个矩阵的行数和列数都相等（即大小形状完全一致） 然后对应位置的数直接相加减得到结果矩阵，结果矩阵的大小形状与初始两个矩阵相同，例如： [1,14,51,4]+[1,91,98,1]=[2,105,149,5]\begin{bmatrix} 1,1\\ 4,5 \\ 1,4 \end{bmatrix}+\begin{bmatrix} 1,9\\ 1,9 \\ 8,1 \end{bmatrix}=\begin{bmatrix} 2,10\\ 5,14 \\ 9,5 \end{bmatrix} 1,14,51,4 + 1,91,98,1 = 2,105,149,5 减法同理。 2、数乘运算 一个数乘一个矩阵，结果是一个矩阵，大小形状与原矩阵的相同。 具体运算过程是用这个数分别乘矩阵的每一个数，例如： 2∗[1,14,51,4]=[2,28,102,8]2* \begin{bmatrix} 1,1\\ 4,5 \\ 1,4 \end{bmatrix}=\begin{bmatrix} 2,2\\ 8,10 \\ 2,8 \end{bmatrix} 2∗ 1,14,51,4 = 2,28,102,8 3、乘法运算 乘法运算的前提是前一个矩阵的行与后一个矩阵的列相等 假设初始矩阵 A 是一个 m∗nm*nm∗n 的矩阵，初始矩阵 B 是一个 n∗pn*pn∗p 的矩阵。 则结果矩阵 C 是一个 m∗pm*pm∗p 的矩阵，且 Ci,j=∑k=1nAi,k∗Bk,jC_{i,j}=\sum_{k=1}^{n} A_{i,k}*B_{k,j} Ci,j =k=1∑n Ai,k ∗Bk,j 有点绕，来看例子你就懂了： [1,14,51,4]⋅[1,9,19,8,1]\begin{bmatrix} 1,1\\ 4,5 \\ 1,4 \end{bmatrix}\cdot\begin{bmatrix} 1,9,1\\ 9,8,1 \end{bmatrix} 1,14,51,4 ⋅[1,9,19,8,1 ] =[1∗1+1∗9,1∗9+1∗8,1∗1+1∗14∗1+5∗9,4∗9+5∗8,4∗1+5∗11∗1+4∗9,1∗9+4∗8,1∗1+4∗1]=\begin{bmatrix} 1*1+1*9,1*9+1*8,1*1+1*1\\ 4*1+5*9,4*9+5*8,4*1+5*1 \\ 1*1+4*9,1*9+4*8,1*1+4*1 \end{bmatrix} = 1∗1+1∗9,1∗9+1∗8,1∗1+1∗14∗1+5∗9,4∗9+5∗8,4∗1+5∗11∗1+4∗9,1∗9+4∗8,1∗1+4∗1 =[10,17,249,76,937,41,5]=\begin{bmatrix} 10,17,2\\ 49,76,9 \\ 37,41,5 \end{bmatrix} = 10,17,249,76,937,41,5 （这里没看懂可以多看几次，自己举个例子） 注意：矩阵乘法不支持交换律！！必须保证前一个矩阵的行与后一个矩阵的列相等！ 来看这道题 直接按照上面的公式模拟就可以了。 上面的matrix结构体部分就是矩阵乘法的模板代码，可以背下来（本人在这类问题中习惯下标从 000 开始） 到此为止，你已经完成了所有铺垫知识的学习，接下来我们步入正题！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 正文 矩阵快速幂是一种技巧，用来优化递推类型（动态规划）的问题。 例题1 一下看到这道题，是不是觉得可以秒掉？这不是初学者就会做的题吗？ 但是一看数据范围： 好吧，直接傻掉了，O(n)O(n)O(n) 的递推根本过不去！ 所以就要用到今天这个算法：矩阵快速幂 我们先做一个大胆的尝试： [1,1]∗[0,11,1]=[1,2]\begin{bmatrix} 1,1\end{bmatrix}*\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}=\begin{bmatrix} 1,2\end{bmatrix} [1,1 ]∗[0,11,1 ]=[1,2 ] 然后 [1,2]∗[0,11,1]=[2,3]\begin{bmatrix} 1,2\end{bmatrix}*\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}=\begin{bmatrix} 2,3\end{bmatrix} [1,2 ]∗[0,11,1 ]=[2,3 ] 还没看出来？再来一个： [2,3]∗[0,11,1]=[3,5]\begin{bmatrix} 2,3\end{bmatrix}*\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}=\begin{bmatrix} 3,5\end{bmatrix} [2,3 ]∗[0,11,1 ]=[3,5 ] ⋯\cdots⋯ 我们发现 111 行 222 列的那个矩阵里面的值就是斐波那契数列（即 FFF 数组）！！！ 总结一个规律，求第 kkk 项，不就是用[1,1]\begin{bmatrix} 1,1\end{bmatrix}[1,1 ] 乘上 [0,11,1]k−1\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}^{k-1}[0,11,1 ]k−1，再取出 111 行 222 列的矩阵的第一个数吗？ 接下来的问题是不是就来到了如何求 [0,11,1]k−1\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}^{k-1}[0,11,1 ]k−1 吗？ 可以使用快速幂！！！ 矩阵快速幂！！！ 看模板代码之前，还要引入一个概念：单位矩阵（相当于累乘器初始化的 111） 它的主对角线为 111，其余地方为 000。（可以自己举几个例子，发现不管它乘什么矩阵，结果都是原来的矩阵） 和正常快速幂没什么区别，就是做运算的底数是矩阵而已。 那么我们就可以解决上面那道例题了，主函数部分： 复杂度：O(k3logn)O(k^3log n)O(k3logn) kkk 为矩阵的行/列数，可忽略。 是不是特别简单？ 可能有读者看到这里会问了，如何知道那个放到快速幂中的 MMM 矩阵是什么呢？每道题的这个矩阵都一样吗？ 别急，通过接下来的这道例题，你会明白如何得到这个 mmm 矩阵。 例题2 这道题看起来和刚刚那道题很像，只是多了个系数。 还是按照刚刚的思路，我们一起来推理一下 mmm 矩阵。 首先我们要先有一个矩阵（向量），里面存储了我们想要的信息。 这道题我们想知道什么呢？ 首先肯定是当前这一项 aka_kak ， 然后还有什么？ 我们需要知道下一项，是不是要知道它前面的两项？所以还要存储一个上一项 ak−1a_{k-1}ak−1 [ak−1,ak]\begin{bmatrix} a_{k-1},a_k\end{bmatrix} [ak−1 ,ak ] 这个向量的初始数据是 [x,y]\begin{bmatrix} x,y\end{bmatrix}[x,y ]（kkk 从 222 开始） 这样就定义好了，就像定义一个状态。接下来要推理 mmm 矩阵。 mmm 矩阵一定是一个行数等于列数的矩阵。 因为它要能和这个向量相乘，需要满足行数和列数都等于这个向量的数据个数（在这里为 222） 因此 mmm 矩阵长这样： [?,??,?]\begin{bmatrix} ?,?\\ ?,? \end{bmatrix} [?,??,? ] 接下来我们看看如何设定 mmm 矩阵使得数据能递推下去，即满足下面这个式子： [ak−1,ak]∗[?,??,?]=[ak,ak+1=p∗an−1+q∗an−2]\begin{bmatrix} a_{k-1},a_k\end{bmatrix}*\begin{bmatrix} ?,?\\ ?,? \end{bmatrix}=\begin{bmatrix} a_k,a_{k+1}=p*a_{n-1}+q*a_{n-2}\end{bmatrix} [ak−1 ,ak ]∗[?,??,? ]=[ak ,ak+1 =p∗an−1 +q∗an−2 ] 不难发现左上角填 000，左下角填 111，右上角填 qqq，右下角填 ppp： [0,q1,p]\begin{bmatrix} 0,q\\ 1,p \end{bmatrix} [0,q1,p ] 这道题基本就做完了。 读者可以尝试自己推导例题一的矩阵。 掌握较熟练后，还可以思考如何求斐波那契前 nnn 项和，前 nnn 项平方和。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 拓展例题 最后来看例题3 这道题看上去非常吓人，有读者可能会考虑高精度，但发现 nnn 最大有 101810^{18}1018，不可行。 考虑 dp。 设 dp[i]dp[i]dp[i] 表示考虑加到第 iii 个数的结果对 mmm 取模，不难得到状态转移方程： dpi=dpi−1∗10x+idp_i=dp_{i-1}*10^x+i dpi =dpi−1 ∗10x+i 其中 xxx 表示 iii 是几位数。 考虑矩阵快速幂优化。 在这里直接给出递推式，请读者自行推演： [dpi,i+1,1]∗[10x,0,01,1,00,1,1]\begin{bmatrix} dp_i,i+1,1 \end{bmatrix}*\begin{bmatrix} 10^x,0,0\\ 1,1,0 \\ 0,1,1 \end{bmatrix} [dpi ,i+1,1 ]∗ 10x,0,01,1,00,1,1 发现 10x10^x10x 会变化，考虑做多次矩阵快速幂，每次做同样位数的范围。 细节比较多，具体看代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 结语 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 终于肝完了，矩阵快速幂还是挺实用的。 其实它类似于一类构造题，需要自己多多练习和领悟。 本文可能有许多没讲懂或没讲全的内容，深感抱歉，但实在是能力有限欢迎提出修改建议。