难度1~10，越大越难 带修莫队和回滚莫队。其实个人感觉回滚莫队的代码还是略微比带修莫队的难度低一些的，但是难度评级不按这一套。带修莫队：4，回滚莫队：3 主席树。应该是上位蓝了。3 可持久化大家族：数组3，并查集感觉复杂了不少5 整体二分：3 FHQ-Treap：3 CDQ：4 CDQ优化DP：5 CDQ套CDQ：7 线段树合并：4

正十七边形尺规作图 一、核心数学基础 1. 可作性依据 17 是费马素数，形式为 F_k = 2 ^ (2^k) + 1，其中 k=2 时 F_2=17。 尺规作图仅能完成线段的和、差、积、商、开平方五种运算。正多边形可尺规作图的充要条件为：边数的质因数仅含 2 和互不相同的费马素数。 2. 单位根与余弦值推导 设圆周角 θ = 2π/17（对应 360°/17），17 次单位根 α_k = cos(kθ) + i·sin(kθ)，满足方程 α_k^17 = 1。 通过高斯分圆理论，将单位根分组求和，逐级解二次方程可得 cosθ： 一级和：x₁ = α₁+α₂+α₄+α₈，x₂ = α₃+α₅+α₆+α₇+α₉+α₁₀+α₁₁+α₁₂ 二级和：y₁ = α₁+α₄，y₂ = α₂+α₈ 三级和：z₁ = α₁+α₁₆，z₂ = α₄+α₁₃ 满足方程组： x₁ + x₂ = -1，x₁·x₂ = -4 y₁ + y₂ = x₁，y₁·y₂ = -1 z₁ + z₂ = y₁，z₁·z₂ = x₂ cosθ = z₁ / 2 最终得到 cosθ 的显式表达式： cos⁡(360∘17)=116(−1+17+34−217+217+317−34−217−234+217)cos⁡(2π17)=116(−1+17+34−217+217+317−34−217−234+217)\cos\left(\frac{360^\circ}{17}\right) = \frac{1}{16}\left( -1 + \sqrt{17} + \sqrt{34 - 2\sqrt{17}} + 2\sqrt{ 17 + 3\sqrt{17} - \sqrt{34 - 2\sqrt{17}} - 2\sqrt{34 + 2\sqrt{17}} } \right) \\\cos\left(\frac{2\pi}{17}\right) = \frac{1}{16}\left( -1 + \sqrt{17} + \sqrt{34 - 2\sqrt{17}} + 2\sqrt{ 17 + 3\sqrt{17} - \sqrt{34 - 2\sqrt{17}} - 2\sqrt{34 + 2\sqrt{17}} } \right)cos(17360∘ )=161 (−1+17 +34−217 +217+317 −34−217 −234+217 )cos(172π )=161 (−1+17 +34−217 +217+317 −34−217 −234+217 ) 二、作图准备 工具 无刻度直尺、圆规 基础图形 1. 作圆 O，半径记为 R； 2. 作圆 O 的水平直径 AB，左端点为 A，右端点为 B； 3. 作圆 O 的垂直直径 CD，上端点为 C，下端点为 D，AB 与 CD 交于圆心 O。 三、分步作图流程 步骤 1：构造基础辅助点 1. 以 B 为圆心，BO 为半径作弧，交圆 O 于 P₁、P₂ 两点； 2. 连接 P₁P₂，交 OB 于 E 点，E 为 OB 中点，OE = EB = R/2； 3. 以 E 为圆心，EC 为半径作弧，交 AO 延长线于 F 点； 由勾股定理得 EC = √(OE² + OC²) = √[(R/2)² + R²] = (√5 R)/2，故 EF = EC； 4. 以 F 为圆心，FE 为半径作弧，交 AB 于 G、H 两点（G 在 F 左侧，H 在 F 右侧），FG = FH = (√5 R)/2。 步骤 2：构造一级和 X₁、X₂ 对应线段 1. 作线段 L_√17：作直角三角形，直角边分别为 R 和 4R，斜边即为 √(R² + (4R)²) = √17 R； 2. 构造 L_x1（对应 x₁）： * 作线段差 L_(-1+√17) = L_√17 - R； * 取 L_(-1+√17) 的中点，得 L_x1 = L_(-1+√17)/2； 3. 构造 L_x2（对应 x₂）： * 作反向线段和 L_(-1-√17) = -(R + L_√17)； * 取 L_(-1-√17) 的中点，得 L_x2 = L_(-1-√17)/2。 步骤 3：构造二级和 Y₁、Y₂ 对应线段 1. 作线段 L_√(x₁²+4)：作直角三角形，直角边为 L_x1 和 2R，斜边即为 √(L_x1² + (2R)²) = √(x₁² + 4)·R； 2. 构造 L_y1（对应 y₁）： * 作线段和 L_(x1+√(x1²+4)) = L_x1 + L_√(x₁²+4)； * 取中点得 L_y1 = L_(x1+√(x1²+4))/2； 3. 构造 L_y2（对应 y₂）： * 作线段差 L_(x1-√(x1²+4)) = L_x1 - L_√(x₁²+4)； * 取中点得 L_y2 = L_(x1-√(x1²+4))/2。 步骤 4：构造三级和 Z₁ 对应线段 1. 作线段 L_√(y₁²-4x₂)：作直角三角形，直角边为 L_y1 和 2L_x2，斜边即为 √(y₁² - 4x₂)·R； 2. 构造 L_z1（对应 z₁ = 2cosθ）： * 作线段和 L_(y1+√(y1²-4x₂)) = L_y1 + L_√(y₁²-4x₂)； * 取中点得 L_z1 = L_(y1+√(y1²-4x₂))/2。 步骤 5：确定正十七边形顶点并完成作图 1. 在直径 AB 上，从圆心 O 向 A 方向截取线段 OM = L_z1 / 2（即 OM = cosθ·R）； 2. 过 M 点作 AB 的垂线，交圆 O 于 P₁ 点，P₁ 即为正十七边形的第一个顶点； 3. 以 P₁ 为圆心，P₁A 为半径作弧，依次在圆 O 上截取 P₂、P₃、...、P₁₇ 共 17 个顶点； 4. 用直尺依次连接 P₁-P₂-P₃-...-P₁₇-P₁，即得到正十七边形。

欢迎大家加入我的小组 https://www.luogu.com.cn/team/121117

欢迎大家加入我的小组 https://www.luogu.com.cn/team/121117

现在团队刚刚创立，没有什么人，如果您想要当可以直接来找我商量，如果您喜欢清静，可以静静的在团队列表之中，希望您可以加入我的团队，《世家》永远是您的家，不会背叛您 如果您想要加入请复制这个网址加入，我真的由衷的感谢您 https://www.acgo.cn/application/1945394452660805632

报上数来，点赞也行

题目描述 在遥远的地方有一条大河，河边有许多村庄。村庄按顺序沿着河流编号为0到M。相邻村庄之间的距离正好是1英里。 米尔科住在标为0的村庄里。他从事用自己的船在村庄之间运送人的生意。今天，米尔科将从他的村庄前往M村，同时他也会沿途运送一些人。 今天有N个人希望出行，我们知道每个人的起点和终点。米尔科的船可以容纳任意数量的人。 比如说，A人从2村前往8村，B人从6村前往4村。和往常一样，米尔科会从他的0村出发，在2村接上A，在6村接上B，回到4村让B下车，继续前往8村让A下车，然后继续前往他的最终目的地M村。这个场景在下面的第一个测试用例中给出。 编写一个程序，求出米尔科为了把所有人送到目的地并最终到达M村必须行驶的最少英里数。 输入格式 输入的第一行包含整数N和M（N≤300000，3≤M≤10^9）。 接下来的N行各包含两个整数，分别是每个想要出行的村民的起点和终点。这些数字的范围在0到M之间。 输出格式 输出米尔科必须行驶的最少英里数。

山河煮岁月，笔墨绘清欢 第一卷 故园旧梦，草木含情 龙河在记忆里永远泛着清浅的波光，那是故乡的脐带，缠绕着李氏家族几代人的晨昏。夏日的河湾是天然的乐园，我们赤足踩进微凉的水流，看阳光碎成金箔铺在水面，听蝉鸣与水声织成少年时代的交响。旱年里，乡亲们扎堆“淘河渗”抗旱，铁锹铲起泥土的声响混着汗水的咸涩，在烈日下酿成最质朴的生存之歌。暮色四合时，人群踏着余晖渡河去看露天电影，身影被夕阳拉得很长，河风里飘着爆米花的甜香与闲谈的笑语，这些琐碎的日常，在时光的窖藏中渐渐沉淀成诗。 村边的水渠悠悠流淌了数十载，是童年最鲜活的注脚。疏渠时“打硪”的号子雄浑有力，震得岸边的野草都跟着摇晃；暴雨过后，我们趁大人不注意，泅渡漫水的渠段，惊起几只水鸟，也惊得母亲在岸边声声呼唤。偶尔偷拔邻居地里的花生，揣在兜里一路狂奔，泥土的芬芳与花生的清甜，是属于乡村少年的隐秘快乐。渠水一年年在流淌，我也一直在成长，那些与水渠相关的日子，早已化作精神的养分，滋养着异乡的漂泊岁月。 老县城的麻石巷道藏着时光的密码，青石板被岁月磨得发亮，每一道纹路都刻着20世纪七八十年代的印记。小猪集的两层小楼里，曾传来商贩的吆喝与孩童的嬉闹；刻着《七律·送瘟神》的石碑立在街角，见证着小城的变迁。第一次进城看病时的忐忑，逛新华书店买下《陈玉成》时的雀跃，在巷道间追逐嬉戏的欢畅，都被老县城温柔接纳。它不像都市那般喧嚣，却以独特的肌理，成为时代记忆的容器，珍藏着最纯粹的少年心事。 故乡的秋总带着别样的清宁。槐树叶底，阳光一丝一丝漏下来，落在破壁腰中蓝白相间的牵牛花上，疏疏落落的秋草作陪，构成一幅天然的水墨小品。清晨的槐蕊铺满台阶，脚踏上去没有声音，只有极微细极柔软的触觉，扫街人留下的扫帚丝纹，细腻中透着清闲，潜意识里还藏着几分落寞。秋蝉的衰弱残声在巷子里回荡，不像南方那般稀罕，反倒像家家户户养着的家虫，为清秋添了几分烟火气。屋角的枣子树结出淡绿微黄的果实，像橄榄又像鸽蛋，在细叶间藏着秋日的丰盈，那是北国清秋独有的Golden Days。 第二卷 山河行旅，心随景阔 北戴河的大海是一场精神的成年礼。初遇时，那片辽阔的蓝撞入眼底，瞬间抚平了内心的褶皱，仿佛婴孩在确认暌违已久的母亲。海风带着咸湿的气息扑面而来，海浪层层叠叠涌向岸边，拍打着礁石，发出雄浑的声响。赤脚踩在沙滩上，沙子的温热与海水的清凉交织，抬头是澄澈的蓝天，低头是被海浪冲刷的贝壳，那一刻忽然顿悟，生命原来可以这般辽阔。所有的迷茫与徘徊，在大海的包容中渐渐消散，只剩下对生活最本真的热爱与敬畏。 池州的齐山藏着自然与人文的交响。摩崖石刻历经岁月侵蚀，字迹依旧苍劲，每一笔都刻着古人的情思与哲思；溶洞里的“阴间地府”造型惟妙惟肖，在幽暗的光线下透着神秘，引人探寻。登山途中，石阶被青苔覆盖，两旁的树木枝繁叶茂，阳光透过枝叶的缝隙洒落，形成斑驳的光影。站在山顶远眺，群山连绵起伏，云雾缭绕其间，恍若仙境。自然的奇景与人文的沉淀在此交融，让人在游览中感受历史的厚重，在沉思中体悟自然的灵秀。 七里峪的秋容是一幅流动的山水长卷。山口初晴时，阳光穿透云层，洒在漫山的草木上，镀上一层金边；溪流从悬崖绝壁上跃下，从茂密丛林间涌出，从纵横沟壑中汇入，唱着欢快的生命之歌。沿着山路前行，山花争奇斗妍，白的、红的、粉的、紫的、黄的，织成绚烂的锦缎；落叶飘入溪流，跳跃着去见证最后的辉煌。峰顶的云雾恍若缥缈的轻纱，浮动在群山之间，将山林笼罩在朦胧的意境中。雨中的七里峪更显雅致，雨丝拍打在树叶与石板路上，韵律清脆可听，仿佛最轻柔的敲打乐，踏着金黄色的石板路前行，人似画中走，神随仙景游。 瓦尔登湖畔的四季藏着生活的真谛。我深入森林，是希望有意识地生活，只面对最基本的事实，吸取生活的所有精髓。春日里，湖边的草木抽新芽，鸟儿在枝头欢唱，万物复苏的生机感染着每一个生命；夏日的湖畔清凉静谧，阳光透过树叶的缝隙洒在水面，波光粼粼，偶有微风拂过，带来草木的清香；秋日的瓦尔登湖澄澈见底，岸边的树木换上金黄的盛装，落叶飘落在湖面，随波荡漾；冬日的湖畔银装素裹，寂静中透着庄严，让人在独处中与自己对话。在这里，生活被简化到最低程度，却收获了最丰盈的精神世界。 第三卷 人间温情，岁月回甘 那位困守工厂的写诗朋友，总在机器的轰鸣声中守护着纯粹的诗心。他的诗作或许不够成熟，却满含对生活的热爱与对理想的执着。我曾以“现实主义”为由劝他放弃，却在看到他眼中的光芒时陷入伦理困境。后来才明白，诗歌从来不是深渊，而是平凡生活中的一束光，是对抗庸常的精神堡垒。那些在深夜写下的诗句，那些在车间里偷偷构思的篇章，都藏着最珍贵的赤诚，提醒着我们，无论生活多么琐碎，都不该放弃对美的追求。 江君的离去如流星划过夜空，短暂却留下永恒的光亮。他是个纯粹的理想主义者，始终带着对生活的热忱与对美好的向往，即便遭遇挫折，也从未改变初心。我们曾一同在月下畅谈理想，一同在雨中漫步街头，那些温馨的片段，如今都成了珍贵的回忆。他的早逝让我深感“物伤其类”的痛感，也让我更加懂得珍惜当下的每一刻。生命或许无常，但理想与热爱会永远流传，如暗夜中的星辰，指引着前行的方向。 父亲的爱藏在平凡的细节里。在学校的课堂上，他声音洪亮，眼里闪烁着兴奋的光芒，将知识传递给一届又一届学生；暑假的午后，他顶着酷暑为我钉被子，汗水浸湿了衣衫，却依旧一丝不苟。记得小时候，我总爱跟着他去学校，在办公室的角落里安静看书，看他批改作业时认真的模样，看他与同事讨论问题时专注的神情。父亲的言传身教，如春雨般润物细无声，教会我善良、坚韧与责任，那些深沉的爱，早已融入我的骨血，成为一生的财富。 与老伴在七里峪的白皮树旁合影时，阳光正好，微风不燥。我们一同承受岁月的风雨，一同踏过人生的坎坷，如今又一同欣赏自然的美景。冒雨下山时，我们相亲相爱地在一起淋雨，雨水打湿了头发与衣衫，心里却满是温暖。婚姻就像一场漫长的旅行，有坦途也有坎坷，有晴天也有雨天，唯有相互扶持、彼此包容，才能走到最后。白皮树的枝叶繁茂，象征着我们坚韧的爱情，愿往后余生，我们仍能携手同行，看遍世间风景，共度岁月流年。 第四卷 书海遨游，心灵栖居 抄书是文学启蒙的必修课，从小学时抄《天仙配》剧本，到中学剪贴报纸副刊，再到大学抄录唐诗宋词，那些笔墨流淌的时光，成了最珍贵的回忆。我总爱用砂纸打磨书口，小心翼翼地揭去旧书的标签，仿佛在与时光对话。鲁迅抄古碑的执着，王勃“海内存知己，天涯若比邻”的豪情，李白“长风破浪会有时”的壮志，杜甫“安得广厦千万间”的悲悯，都通过笔墨的传递，深深印在我的心底。抄书的过程，不仅是对文字的记忆，更是与先贤的精神对话，让我在潜移默化中汲取文学的滋养。 唐诗如清泉，如美酒，饮之有一种说不出的美妙之感。少年时误读王勃《山中》的“将”字，如今想来仍觉有趣；长大后通读李杜诗选，才真正体会到唐诗的博大精深。“大漠孤烟直，长河落日圆”的雄浑壮阔，“明月松间照，清泉石上流”的清新雅致，“春蚕到死丝方尽，蜡炬成灰泪始干”的深情执着，每一首诗都如一幅画、一首歌，引领着我走进不同的意境。唐诗不仅是文学瑰宝，更成为我的精神坐标系，在迷茫时给予指引，在失意时给予慰藉。 《故都的秋》让我读懂了秋的深味。郁达夫笔下的北国之秋，来得清，来得静，来得悲凉，陶然亭的芦花，钓鱼台的柳影，西山的虫唱，玉泉的夜月，潭柘寺的钟声，都是故都秋味的注脚。在北平租一椽破屋，泡一碗浓茶，坐在院子里细数漏下的日光，静对牵牛花与秋草，那种清闲与落寞，是南国之秋无法比拟的。正如作者所言，北国之秋若留得住，愿折去寿命的三分之二，换得一个三分之一的零头。这样的文字，如秋日的清风，拂去心灵的尘埃，让人在沉静中感受生命的厚度。 《荷塘月色》的清丽文字，是中国现代散文的巅峰之作。曲曲折折的荷塘上面，田田的叶子如亭亭的舞女的裙，零星的白花袅娜地开着，羞涩地打着朵儿，如明珠，如星星，如刚出浴的美人。微风过处，缕缕清香仿佛远处高楼上渺茫的歌声，这种通感的妙用，营造出如梦似幻的意境。在月色笼罩下的荷塘，作者寄托了对宁静美好境界的向往，那些细腻的描写，如涓涓细流，流淌在读者的心底，让人在喧嚣的尘世中，寻得一处心灵的宁静港湾。 海伦·凯勒的《假如给我三天光明》，是一曲对生命的赞歌。尽管身处黑暗与无声的世界，她却对生活充满热爱，对光明无比渴望。她提议开设“如何使用你的眼睛”的课程，教人们从最平凡的事物中获取乐趣，这提醒着我们这些视觉正常的人，不要辜负上天的赐予。生活中的美无处不在，只是需要我们用心去发现、去感受。无论是清晨的第一缕阳光，还是傍晚的漫天晚霞，无论是路边的一朵小花，还是枝头的一只小鸟，都值得我们驻足欣赏。学会珍惜，学会感恩，才能让生活变得更加丰富而有意义。 第五卷 岁月踯躅，向光而行 人生如踯躅前行，既有兜兜转转的徘徊，也有缓慢前行的坚韧。那些走过的路，有坦途也有坎坷；那些遇见的人，有温暖也有疏离；那些经历的事，有喜悦也有遗憾。但正是这些点点滴滴，构成了独一无二的人生。就像龙河在岁月中流淌，有时平缓，有时湍急，却始终向着远方；就像悬崖缝隙中的树木，风雨如磐，却依旧挺直腰杆，坚守着大山。踯躅不是退缩，而是在沉淀中积蓄力量，在反思中明确方向。 岁月如烟，许多事情都已消逝在时光的长河中，但那些触动心灵的瞬间，那些温暖人心的记忆，却如陈年佳酿，愈久愈香。旧报纸上的文字依然清晰，仿佛刚刚出版；老照片里的笑容依旧灿烂，仿佛就在昨天；抄过的诗集依然完好，仿佛笔墨未干。这些珍贵的遗存，是时光的见证，是心灵的慰藉，让我们在速朽的时代，得以回望过往，汲取前行的力量。 在这个快节奏的时代，我们常常被喧嚣裹挟，被焦虑困扰，忘记了慢下来感受生活的美好。其实，生活不必太过匆忙，不妨学梭罗那样，深深地生活，吸取生活的所有精髓；不妨学郁达夫那样，静下心来，感受季节的变迁；不妨学那些散文大家，在自然中寻找灵感，在书籍中寻找慰藉，在亲情中感受温暖。慢下来，才能发现生活的诗意；静下来，才能听见心灵的声音。 愿我们都能在山河岁月中，守住内心的澄澈；在人间烟火中，珍藏温情与感动；在书海遨游中，丰富精神世界；在踯躅前行中，始终向着光明。无论经历多少风雨，都能保持对生活的热爱，对美好的向往，让每一个平凡的日子，都绽放出独特的光彩。毕竟，人间值得，未来可期，那些走过的路，读过的书，爱过的人，都会成为生命中最珍贵的财富，指引我们在人生的旅途中，坚定前行，温暖向善。

1. 书页翻动的声音，是灵魂与智慧的私语。 2. 人生如四季流转，既有春暖花开的欢欣，也有冬雪覆地的沉静，每个阶段都值得珍藏。 3. 勇气不是没有恐惧，而是明知前方艰难仍选择前行的那份坚定。 4. 友谊如同古树年轮，在岁月的沉淀中愈发坚实而深刻。 5. 善良是种选择，它让平凡的生命散发出非凡的光芒。 6. 在书香中漫步，每一页都是与伟大灵魂的邂逅。 好

https://hmcl.huangyuhui.net/

刘存浩:俞哥，你真的什么都不记得了吗【大哭】 谢俞：嗯 刘存浩：那你还记得贺朝吗？ 谢俞：不记得，他是什么很重要的人吗？ 刘存浩:对对对他特别重要 （此时贺朝故意从病房前走过） 刘存浩：俞哥，你现在有没有一种一见钟情的感觉【期待】 谢俞：没有，我只是很想上去和他打一架 刘存浩内心os：他怎么不按常理出牌啊 贺朝内心os：得，又要重新追小朋友了

发育 相信新手皇帝已经蒙了/迫不及待了（相信你们会无语） 不知到你们有没有这种感觉，上天让你坐在电脑前看这篇文章简直是个奇迹，你看： 只要秦始皇没统一中国，现在会怎么样呢？ 只要汉朝没有休养生息，透支国力，当时的外面会对中国怎么样？ 只要元朝没有那个壮志闯荡世界，那现在中国的领土能多大呢？ 只要鸦片战争，第一、二次世界大战，日本侵华，抗美援朝，我们失败会怎们样？ 学过历史的都知道（没学过的现在知道了）：任何乱世都是为新的统一做铺垫，朝代会更替，那么现在的中国又是在为谁做铺垫呢？（这不是悲观，或污蔑祖国，毕竟没有一个中国人不爱国，对吧？但值得深思啊！） 帅吧？ 扯正事了！！ 普通发育： 玩竞赛！（每周六发放竞赛，持续一周，冠军下一朝代（考试人数大于2）） 高级发育： 1. 看题库 2. 竞赛（1个月第一个周六一次，冠亚军下两个朝代！） 随着等级升高，权限也升高哦！ 因团队正在初级，其他功能待开发，皇帝们提提建议！ 我和“中国历史”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！

题目描述 Farmer John（又）想到了一个新的奶牛晨练方案！ 如同之前，Farmer John 的 NNN 头奶牛站成一排。对于 1≤i≤N1\le i\le N1≤i≤N 的每一个 iii，从左往右第 iii 头奶牛的编号为 iii。他告诉她们重复以下步骤，直到奶牛们与她们开始时的顺序相同。 给定长为 NNN 的一个排列 AAA，奶牛们改变她们的顺序，使得在改变之前从左往右第 iii 头奶牛在改变之后为从左往右第 AiA_iAi 头。 例如，如果 A=(1,2,3,4,5)A=(1,2,3,4,5)A=(1,2,3,4,5)，那么奶牛们总共进行一步就回到了同样的顺序。如果 A=(2,3,1,5,4)A=(2,3,1,5,4)A=(2,3,1,5,4)，那么奶牛们总共进行六步之后回到起始的顺序。每步之后奶牛们从左往右的顺序如下： 0 步：(1,2,3,4,5)(1,2,3,4,5)(1,2,3,4,5) 1 步：(3,1,2,5,4)(3,1,2,5,4)(3,1,2,5,4) 2 步：(2,3,1,4,5)(2,3,1,4,5)(2,3,1,4,5) 3 步：(1,2,3,5,4)(1,2,3,5,4)(1,2,3,5,4) 4 步：(3,1,2,4,5)(3,1,2,4,5)(3,1,2,4,5) 5 步：(2,3,1,5,4)(2,3,1,5,4)(2,3,1,5,4) 6 步：(1,2,3,4,5)(1,2,3,4,5)(1,2,3,4,5) 请你计算出所有可能的 N!N!N! 种长为 NNN 的排列 AAA 回到起始顺序需要的步数的乘积。 由于这个数字可能非常大，输出答案模 MMM 的余数（108≤M≤109+710^8\le M\le 10^9+7108≤M≤109+7，MMM 是质数）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 使用 C++ 的选手可以使用 KACTL 中的这一代码。这一名为 Barrett 模乘 的算法可以以比通常计算快上数倍的速度计算 a%ba \% ba%b，其中 b>1b>1b>1 为一个编译时未知的常数。（不幸的是，我们没有找到对于 Java 的这样的优化）。（译注：中文选手可以参考 几种取模优化方法（译自 min-25 的博客）） 输入格式 输入一行包含 NNN 和 MMM。 输出格式 输出一个整数。 输入输出样例 #1 输入 #1 输出 #1 说明/提示 样例解释： 对于每一个 1≤i≤N1\le i\le N1≤i≤N，以下序列的第 iii 个元素等于奶牛需要使用 iii 步的排列数量：[1,25,20,30,24,20][1,25,20,30,24,20][1,25,20,30,24,20]。所以答案等于 11⋅225⋅320⋅430⋅524⋅620≡369329541(mod109+7)1^1\cdot 2^{25}\cdot 3^{20}\cdot 4^{30}\cdot 5^{24}\cdot 6^{20}\equiv 369329541\pmod{10^9+7}11⋅225⋅320⋅430⋅524⋅620≡369329541(mod109+7)。 注意：这个问题的内存限制增加为 512 MB。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 对于 100%100\%100% 的数据，满足 1≤N≤75001\le N\le 75001≤N≤7500。 共 161616 个测试点，其中 111 为样例，其余性质如下： 测试点 222 满足 N=8N=8N=8。 测试点 3∼53\sim 53∼5 满足 N≤50N\le 50N≤50。 测试点 6∼86\sim 86∼8 满足 N≤500N\le 500N≤500。 测试点 9∼129\sim 129∼12 满足 N≤3000N\le 3000N≤3000。 测试点 13∼1613\sim 1613∼16 没有额外限制。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 出题人：Benjamin Qi

P4727 [HNOI2009] 图的同构计数 题目背景 当学生们遇到某个难题时经常会说“这怎么做，这不是 NP 问题吗？”、“这个只有搜了，这己经被证明是 NP 问题了”。但是，你应该清楚，大多数人此时所说的 NP 问题其实都是指 NPC 问题。很多人没有真正掌握 NP 问题和 NPC 问题这两个基本概念。其实 NP 问题并不是那种“只有搜才行”的问题，NPC 问题才是。 很久以前就有一个古老的传说：有―个著名的问题，即 P 是否等于 NP 的问题，传说中谁要是证明或者证伪了这个命题，他将获得幸福。这里 P 是指能在多项式时间里求解的问题的集合。而 NP 是指可在多项式时间里验证的问题的集合。显然 P 是 NP 的子集，因为能在多项式时间里求解的问题，必定可在多项式时间里验证。 到目前为止还没有人因这个命题得到幸福。但是，有一个总的趋势，也就是人们普遍认为，P=NPP=NPP=NP 不成立，即，多数人相信，至少存在一个不可能有多项式时间复杂度的求解算法的 NP 问题。人们如此坚信 P≠NPP \neq NPP=NP 是有原因的，因为在研究 NP 问题的过程中找出了一类非常特殊的 NP 问题叫做 NP-完全问题，也就是所谓的 NPC 问题。正是因为存在 NPC 问题，才使人们相信 P≠NPP \neq NPP=NP。 在提出 NPC 的概念之后，绝大多数“自然”的难题最后都被证明是 NPC 问题，只有三个例外，它们分别是： * 线性规划问题； * 图同构问题； * 素数判定问题与大数分解问题。 题目描述 小雪在了解到以上情况后，自认为直接挑战终极难题还有不少困难，于是决定先从简单的问题做起，具体来说，他对图同构问题产生了浓厚的兴趣。AAA 图与 BBB 图被认为是同构的是指：AAA 图的顶点经过一定的重新标号以后，AAA 图的顶点集和边集要完全与 BBB 图一一对应。 小雪现在专注于如何判断两个图是否同构，同时他还想知道两两互不同构的含 NNN 个点的图有多少种。众所周知含 NNN 个点的简单图最多有 N×(N−1)/2N\times(N-1)/2N×(N−1)/2 条边，这样含 NNN 个点的图有 2N×(N−1)/22^{N\times(N-1)/2}2N×(N−1)/2 种可能的情况。显然这些图中有很多图是同构的，小雪想知道的便是：若同构的图算成一种，则有多少种不同的图。他把这个任务丢给了你，在他想出来之前快点解决吧！ 输入格式 输入包含一个非负整数 NNN，表示图的顶点数，且 0≤N≤600 \leq N \leq 600≤N≤60。 输出格式 输出包含一个整数，表示含 NNN 个点的图在同构意义下不同构的图的数目。因为答案可能很大，所以输出的最终答案是  mod  997\bmod ~ 997mod 997 的结果（997997997 是一个素数）。 输入输出样例 #1 输入 #1 输出 #1 输入输出样例 #2 输入 #2 输出 #2 输入输出样例 #3 输入 #3 输出 #3 输入输出样例 #4 输入 #4 输出 #4 输入输出样例 #5 输入 #5 输出 #5 说明/提示 对于 40%40 \%40% 的数据，N≤20N \le 20N≤20。 对于 100%100 \%100% 的数据，0≤N≤600 \le N \le 600≤N≤60。

P5423 [USACO19OPEN] VALLEYS P 题目描述 Bessie 喜欢观光，而今天她正在寻找景色优美的山谷。 她感兴趣的是一个 $ N \times N $ 的方阵，其中每个格子都有一个高度。所有在此正方形方阵之外的格子的高度可以被看作是无限大。 山谷指的是一块连续、不含洞的一块区域，并且每个相邻的包围该区域的格子都高于这块区域中的所有格子。 更形式化地说： * 一组格子被称作是“沿边相邻的”，如果可以从其中任意一个格子出发，经过一些沿上、下、左、右方向的移动，到达其中所有其他格子。 * 一组格子被称作是“沿点相邻的”，如果可以从其中任意一个格子出发，经过一些沿上、下、左、右、对角线方向的移动，到达其中所有其他格子。 * 一个“区域”指的是一组非空并且沿边相邻的格子。 * 一个区域被称作是“有洞的”，如果这个区域的补集（包括在 $ N \times N $ 方阵之外的无限高格子）不是沿点相邻的。 * 区域的“边界”指的是所有与该区域内的某个格子正交相邻（上、下、左、右），但本身不在该区域内的格子。 * 一个“山谷”指的是某个非有洞区域，满足区域内的任意格子的高度低于该区域边界上任意格子的高度。 Bessie 的目标是求出所有山谷的大小之和。 一些例子 这是一个区域： 这不是一个区域（中间的格子和右下角的格子不沿边相邻）： 这是一个非有洞区域： 这是一个有洞的区域（“甜甜圈”中间的格子与区域外的格子不沿点相邻）： 这是另一个非有洞区域（中间的格子与右下角的格子沿点相邻）： 输入格式 输入的第一行包含 $ N $ ，其中 $ 1 \leq N \leq 750 $ 。 以下 $ N $ 行每行包含 $ N $ 个整数，为方阵每个格子的高度。所有高度 $ h $ 满足 $ 1 \leq h \leq 10^6 $ 。所有高度均为不同的整数。 输出格式 输出一个整数，为所有山谷的大小之和。 输入输出样例 #1 输入 #1 输出 #1 说明/提示 在这个例子中，有三个大小为1的山谷： 一个大小为2的山谷： 一个大小为3的山谷： 一个大小为6的山谷： 一个大小为7的山谷： 以及一个大小为9的山谷： 所以，答案为1 + 1 + 1 + 2 + 3 + 6 + 7 + 9 = 30。 子任务 对于至少19%的测试数据， $ N \leq 100 $ 。

来团队

P1130 红牌 题目描述 某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂 ，一共包括 NNN 个步骤。每一步骤都由政府的某个工作人员负责检查你所提交的材料是否符合条件。为了加快进程，每一步政府都派了 MMM 个工作人员来检查材料。不幸的是，并不是每一个工作人员效率都很高。尽管如此，为了体现“公开政府”的政策，政府部门把每一个工作人员的处理一个申请所花天数都对外界公开。 为了防止所有申请人都到效率高的工作人员去申请。这 M×NM \times NM×N 个工作人员被分成 MMM 个小组。每一组在每一步都有一个工作人员。申请人可以选择任意一个小组也可以更换小组。但是更换小组是很严格的，一定要相邻两个步骤之间来更换，而不能在某一步骤已经开始但还没结束的时候提出更换，并且也只能从原来的小组 III 更换到小组 I+1I+1I+1，当然从小组 MMM 可以更换到小组 111。对更换小组的次数没有限制。 例如：下面是 333 个小组，每个小组 444 个步骤工作天数： * 小组 111： 2,6,1,82, 6 ,1 ,82,6,1,8； * 小组 222：3,6,2,63,6, 2, 63,6,2,6； * 小组 333：4,2,3,64, 2 ,3 ,64,2,3,6。 例子中，可以选择小组 111 来完成整个过程一共花了2+6+1+8=172+6+1+8=172+6+1+8=17 天，也可以从小组 222 开始第一步，然后第二步更换到小组 333，第三步到小组 111，第四步再到小组 222，这样一共花了 3+2+1+6=123+2+1+6=123+2+1+6=12 天。你可以发现没有比这样效率更高的选择。 你的任务是求出完成申请所花最少天数。 输入格式 第一行是两个正整数 NNN 和 MMM，表示步数和小组数。 接下来有 MMM 行，每行有 NNN 个非负整数，第 i+1(1≤i≤M)i+1(1 \le i \le M)i+1(1≤i≤M) 行的第 jjj 个数表示小组 iii 完成第 jjj 步所花的天数，天数都不超过 100000010000001000000。 输出格式 一个正整数，为完成所有步所需最少天数。 输入输出样例 #1 输入 #1 输出 #1 说明/提示 对于 100%100\%100% 的数据，1≤N,M≤20001\le N,M \le 20001≤N,M≤2000。

我的团队

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { }