0103abc

CF622F The Sum of the k-th Powers 题解

发布于 2025-11-08 22:47 104 字 1 min read

0103abc

0103abc 的个人网站，记录算法题解、做题过程与学习笔记。

488 文章 6 分类 74 标签

AGC047E Product Simulation 题解 AGC041C Domino Quality 题解 P17781 千早爱音不是罪过题解 P17802 [CXOI2026] 想要变成鹰的鱼题解 P17801 [CXOI2026] 大潘小潘向前 p 题解 P17800 [CXOI R7-D] 使一颗心不免哀伤题解 P17798 [CXOI R7-B2] 晴涵梦（Hard Version）题解 P17796 [CXOI R7-A] 追忆岁月题解 P17797 [CXOI R7-B1] 晴涵梦（Easy Version）题解 P3838 [IOI 2017] Toy Train 题解 P14238 [CCPC 2024 Shandong I] 三角形题解 P15942 [JOI Final 2026] 赌场 / Casino 题解 P13184 [GCJ 2017 Finals] Teleporters 题解 P17571 「FAOI-R(-2)」数列计数 2024 题解 P17618 [Math+Girl×1] dancing With Myself in the sunset / Wheels Mst 题解 CF2262E Paired Bracket Sequences 题解 CF2246F Whoname and Unsorted Array 题解 CF2248F Matrix Elimination 题解 AT_arc227_f [ARC227F] Erase and Raise 题解 P15992 [PA 2026] 原题加强 2 / Wersja dla profesjonalistów 2 题解 P14490 [集训队互测 2018] 小修和小栋猜数字题解 P15001 摧毁时间线题解 CF955F Heaps 题解 AT_arc226_d [ARC226D] Penta-Queue 题解 AT_arc086_c [ARC086E] Smuggling Marbles 题解 P13708 [NWERC 2023] Isolated Island 题解 P9483 [NOI2023] 合并书本题解 CF2245G NPC Challenge 题解 CF1354G Find a Gift 题解 CF1266F Almost Same Distance 题解 CF1976F Remove Bridges 题解 CF1633F Perfect Matching 题解 CF1303G Sum of Prefix Sums 题解 CF1307F Cow and Vacation 题解 CF1413F Roads and Ramen 题解 CF1957F2 Frequency Mismatch (Hard Version) 题解 P10546 [THUPC 2024 决赛] 采矿题解 P11018 Monochrome Tree 题解 P11149 [THUWC 2018] 城市规划题解 P12692 BZOJ3784 树上的路径题解 P14828 彻彻崩题解 P15076 [ICPC 2024 Chengdu R] Disrupting Communications 题解 P17141 [NOI 2026] 传送题解 P5327 [ZJOI2019] 语言题解 P6018 [Ynoi2010] Fusion tree 题解 CF1572D Bridge Club 题解 CF1268E Happy Cactus 题解 CF1299D Around the World 题解 P14383 [JOISC 2017] 港口设施 / Port Facility 题解 P14019 [ICPC 2024 Nanjing R] 地铁题解 AT_utpc2023_p Priority Queue 3 题解 CF1264E Beautiful League 题解 AT_agc036_f [AGC036F] Square Constraints 题解 P11613 [PA 2016] 覆盖 / Pokrycia 题解 P13153 [GCJ 2018 Finals] Jurisdiction Restrictions 题解 P10896 移言丁真：Unavoided linyue 题解 P11284 「GFOI Round 2」Strings 题解 AT_agc029_f [AGC029F] Construction of a tree 题解 AT_agc038_f [AGC038F] Two Permutations 题解 AT_agc056_c [AGC056C] 01 Balanced 题解 AT_arc158_d [ARC158D] Equation 题解 CF1061E Politics 题解 CF1146G Zoning Restrictions 题解 CF1278F Cards 题解 CF1286E Fedya the Potter Strikes Back 题解 CF1525F Goblins And Gnomes 题解 CF1548C The Three Little Pigs 题解 CF1762E Tree Sum 题解 CF1765C Card Guessing 题解 CF1766F MCF 题解 CF1842G Tenzing and Random Operations 题解 CF2068K Amusement Park Rides 题解 CF708D Incorrect Flow 题解 CF843E Maximum Flow 题解 P10573 [JRKSJ R8] C0mp0nents 题解 P10992 [蓝桥杯 2023 国 Python A] 最长同类子串题解 P11531 [THUPC 2025 初赛] 检查站题解 P13583 [NWRRC 2023] Colorful Village 题解 P14170 二分图最大匹配期望题解 P14368 [JOISC 2018] 修行 / Asceticism 题解 P4055 [JSOI2009] 游戏题解 P4152 [WC2014] 时空穿梭题解 P5287 [HNOI2019] JOJO 题解 P5770 [JSOI2016] 无界单词题解 P6031 CF1278F Cards 加强版题解 P6698 [BalticOI 2020] 病毒 (Day2) 题解 P7361 「JZOI-1」拜神题解 P9374 「DROI」Round 2 单图题解 P9523 [JOIST 2022] 复制粘贴 3 / Copy and Paste 3 题解 P9682 Electro Master 题解 P12468 [Math×Girl] 距离题解 CF1101F Trucks and Cities 题解 CF1392G Omkar and Pies 题解 CF1442D Sum 题解 CF1780E Josuke and Complete Graph 题解 CF845F Guards In The Storehouse 题解 P10084 [GDKOI2024 提高组] 计算题解 P10085 [GDKOI2024 提高组] 染色题解 P11425 [清华集训 2024] 路南柯题解 P11444 [Code+#6] 祖玛题解 P11458 [USACO24DEC] All Pairs Similarity P 题解 P11459 [USACO24DEC] It's Mooin' Time P 题解 P11678 [USACO25JAN] Watering the Plants P 题解 P12074 [OOI 2025] The arithmetic exercise 题解 P12706 蜜蜂构造题题解 P13691 [CEOI 2025] highest 题解 P13939 [EC Final 2019] Black and White 题解 P14106 [ZJCPC 2017] Yet Another Game of Stones 题解 P14198 [ICPC 2024 Hangzhou R] Let's Go! New Adventure 题解 P14344 [JOISC 2019] 两道料理 / Two Dishes 题解 P14347 [JOISC 2019] 灯 / Lamps 题解 P14388 [JOISC 2017] 长途巴士 / Long Distance Coach 题解 P15077 [ICPC 2024 Chengdu R] Double 11 题解 P15108 白井黑子题解 P15301 [ROI 2012 Day 2] army 汗国军队题解 P16160 [ICPC 2016 NAIPC] Jewel Thief 题解 P16329 bloom 题解 P3665 [USACO17OPEN] Switch Grass P 题解 P5400 [CTS2019] 随机立方体题解 P6965 [NEERC 2016] Binary Code 题解 P7843 「C.E.L.U-03」布尔题解 P7985 [USACO21DEC] Paired Up P 题解 P9139 [THUPC 2023 初赛] 喵了个喵 II 题解 P9225 「PEOI Rd1」寻宝（treasure）题解 P9338 [JOIST 2023] 合唱 / Chorus 题解 P9962 [THUPC 2024 初赛] 一棵树题解 P3421 [POI 2005] SKO-Knights 题解 P13540 [IOI 2025] 羊驼的坎坷之旅（obstacles）题解 P6794 [SNOI2020] 水池题解 P5101 [JOI 2017 Final] 绳 / Rope 题解 P9499 「RiOI-2」change 题解 P2145 [JSOI2007] 祖玛题解 CF2245F Familiar? 题解 CF1239B The World Is Just a Programming Task (Hard Version) 题解 P10803 [CEOI 2024] 文本编辑器题解 CF1312G Autocompletion 题解 AT_agc049_d [AGC049D] Convex Sequence 题解 AT_abc257_h [ABC257Ex] Dice Sum 2 题解 AT_abc270_h [ABC270Ex] add 1 题解 AT_arc165_e [ARC165E] Random Isolation 题解 CF1025G Company Acquisitions 题解 CF1349D Slime and Biscuits 题解 CF1392F Omkar and Landslide 题解 CF1733E Conveyor 题解 CF1819D Misha and Apples 题解 CF1823F Random Walk 题解 CF1919F2 Wine Factory (Hard Version) 题解 CF436E Cardboard Box 题解 CF850F Rainbow Balls 题解 CF869E The Untended Antiquity 题解 P10587 「ALFR Round 2」C 小 Y 的数题解 P11191 「KDOI-10」超级演出题解 P11660 我终将成为你的倒影题解 P12479 [集训队互测 2024] 长野原龙势流星群题解 P12587 「KTSC 2019 R2」外星仙人掌题解 P13552 鱼类考古学题解 P13780 「o.OI R2」愿天堂没有分块题解 P14268 [ROI 2015 Day2] 路灯题解 P14761 [Opoi 2025] CCD 的序列题解 P15672 [ICPC 2024 Jakarta R] Narrower Passageway 题解 P17145 [NOI 2026] 彩虹树题解 P2235 [HNOI2002] Kathy函数题解 P2284 [HNOI2003] 密室之门题解 P2305 [NOI2014] 购票题解 P3345 [ZJOI2015] 幻想乡战略游戏题解 P3546 [POI 2012] PRE-Prefixuffix 题解 P3706 [SDOI2017] 硬币游戏题解 P3920 [WC2014] 紫荆花之恋题解 P4098 [HEOI2013] ALO 题解 P4220 [WC2018] 通道题解 P4292 [WC2010] 重建计划题解 P5278 算术天才⑨与等差数列题解 P5524 [Ynoi2012] NOIP2015 充满了希望题解 P5953 [POI 2018] Różnorodność 题解 P7215 [JOISC 2020] 首都题解 P8684 [蓝桥杯 2019 省 B] 灵能传输题解 P9965 [THUPC 2024 初赛] 转化题解 P14606 [NWRRC 2025] Games of Chess 题解 P11164 [BalkanOI 2023] Permutations 题解 P14211 [ROI 2016 Day2] 快递服务题解 P13618 [ICPC 2024 APC] Bánh Bò 题解 CF2242F Summer Vacation 题解 CF2242E Product of Closures 题解 P17064 [JRKSJ R10 热身赛] Infinite Strife, 题解 P10103 [GDKOI2023 提高组] 错排题解 CF1033E Hidden Bipartite Graph 题解 P17002 [NWERC 2019] 无用交换机 / Disposable Switches 题解 CF493E Vasya and Polynomial 题解 P11812 [PA 2015] 精确打击 / Kontrmanifestacja 题解 P16942 「LAOI-18」铃喵题解 P11815 [PA 2019 Final] 领地 / Terytoria 题解 CF1450E Capitalism 题解 CF1654F Minimal String Xoration 题解 P1001 A+B Problem 题解 P14510 夜里亦始终想念着你 miss 题解 P16910 「MierOI R2」靈题解 P15419 「yrOI R1」冬日永恒题解 CF1884E Hard Design 题解 P15421 像你这样的朋友题解 P16637 春季限定独立集问题题解 P15479 [CERC2012] Non-boring sequences 题解 CF1107F Vasya and Endless Credits 题解 CF1260F Colored Tree 题解 CF1129C Morse Code 题解 P5904 [POI 2014] HOT-Hotels 加强版题解 P12866 [JOI Open 2025] 抽奖 / Lottery 题解 P12441 [NERC2023] Joy of Pokémon Observation 题解 CF1418F Equal Product 题解 P16362 [BalticOI 2026] Sort 题解 P16433 [APIO 2026 中国赛区] 上升题解 CF1325F Ehab's Last Theorem 题解 P12293 [蓝桥杯 2024 国 Java A] 合并小球题解 P11288 [COTS 2017] 模板 Z1 题解 P12936 [NERC 2019] Cactus Revenge 题解 P16357 [BalticOI 2026] Blocks 题解 P13233 [GCJ 2015 Finals] Costly Binary Search 题解 AT_arc136_d [ARC136D] Without Carry 题解 CF1508E Tree Calendar 题解 P9850 [ICPC 2021 Nanjing R] Ancient Magic Circle in Teyvat 题解 P6766 [APIO2020] 有趣的旅途题解 CF1444C Team-Building 题解 P6009 [USACO20JAN] Non-Decreasing Subsequences P 题解 AT_arc122_d [ARC122D] XOR Game 题解 AT_abc450_g [ABC450G] Random Subtraction 题解 P15502 [ICPC 2025 APC] Book Sorting 题解 P15555 [CCPC 2025 哈尔滨站] 比赛题解 CF850D Tournament Construction 题解 CF1404D Game of Pairs 题解 CF1545C AquaMoon and Permutations 题解 CF1830D Mex Tree 题解 CF1379E Inverse Genealogy 题解 CF1612G Max Sum Array 题解 CF1613F Tree Coloring 题解 CF1620F Bipartite Array 题解 CF1622F Quadratic Set 题解 AT_arc127_e [ARC127E] Priority Queue 题解 CF1632E2 Distance Tree (hard version) 题解 CF1582G Kuzya and Homework 题解 CF1623E Middle Duplication 题解 CF1679F Formalism for Formalism 题解 CF1626F A Random Code Problem 题解 CF1734F Zeros and Ones 题解 P15653 [省选联考 2026] 星图题解 AT_agc071_c [AGC071C] Orientable as Desired 题解 CF1097G Vladislav and a Great Legend 题解 CF1579G Minimal Coverage 题解 CF1598F RBS 题解 CF1614D1 Divan and Kostomuksha (hard version) / CF1614D2 Divan and Kostomuksha (hard version) 题解 CF1768E Partial Sorting 题解 CF2204G Grid Path 题解 CF521D Shop 题解 CF852A Digits 题解 P15741 [JAG 2024 Summer Camp #2] Max Sum of GCD 题解 P15761 [JAG 2025 Summer Camp #1] Colored Tree and Path 题解 P3644 [APIO2015] 巴邻旁之桥题解 CF1656F Parametric MST 题解 CF1906C Cursed Game 题解 CF331D3 Escaping on Beaveractor 题解 CF1975G Zimpha Fan Club 题解 CF641F Little Artem and 2-SAT 题解 CF1344F Piet's Palette 题解 CF1381D The Majestic Brown Tree Snake 题解 CF1411F The Thorny Path 题解 CF1408H Rainbow Triples 题解 P15416 「yrOI R1」夏日已逝题解 P15265 [USACO26JAN2] Dynamic Instability P 题解 AT_awc0001_a バクテリアの増殖実験题解 P15235 「CROI · R3」浣熊的小游戏题解 P10741 [SEERC 2020] Fence Job 题解 AT_ajo2024_final_c Final Exam 题解 P9535 [YsOI2023] 连通图计数题解 P15191 [SWERC 2019] Pseudo-Random Number Generator 题解 SP27098 FN16OIL - Oil 题解 P1691 [ICPC 2016 WF] Oil 题解 CF1776I Spinach Pizza 题解 P15164 [SWERC 2022] Spinach Pizza 题解 CF1730D Prefixes and Suffixes 题解 CF1693D Decinc Dividing 题解 CF1144G Two Merged Sequences 题解 CF1600F Party Organization 题解 CF1929E Sasha and the Happy Tree Cutting 题解 P5172 [清华集训 2014] Sum 题解 P12417 基础构造练习题 1 题解 CF1691F K-Set Tree 题解 CF2048G Kevin and Matrices 题解 P10871 [COTS 2022] 皇后 Kraljice 题解 P14610 [NWRRC 2025] Keys and Grates 题解 P14564 圆环题解 P14421 [JOISC 2014] 拉面比较 / Ramen 题解 P14300 [JOI2023 预选赛 R2] 货物列车 / Freight Train 题解 P14415 [JOISC 2015] 遗产继承 / Inheritance 题解 P7974 [KSN2021] Delivering Balls 题解 P10665 [AMPPZ2013] Bytehattan 题解 P9920 「RiOI-3」变换，反演题解 P10045 [CCPC 2023 北京市赛] 线段树题解 P6012 [P5087] 数学加强版题解 CF2085F2 Serval and Colorful Array (Hard Version) 题解 P10756 [COI 2023] Sličnost 题解 P3641 [APIO2016] 最大差分题解 P6790 [SNOI2020] 生成树题解 P10832 [COTS 2023] 传 Mapa 题解 P14449 [ICPC 2025 Xi'an R] Catch the Monster 题解 P14315 [Aboi Round 2] Faputa 题解 P5667 拉格朗日插值2 题解 CF2163D1 Diadrash (Easy Version) 题解 CF2163D2 Diadrash (Hard Version) 题解 CF622F The Sum of the k-th Powers 题解 P11536 [NOISG 2023 Finals] Curtains 题解 P11620 [Ynoi Easy Round 2025] TEST_34 题解 P14455 [ICPC 2025 Xi'an R] Imagined Holly 题解 P1993 小 K 的农场题解 P3430 [POI 2005] DWU-Double-row 题解 P5290 [十二省联考 2019] 春节十二响题解 P5395 第二类斯特林数·行题解 P5396 第二类斯特林数·列题解 P5408 第一类斯特林数·行题解 P6130 随机红包题解 P6898 [ICPC 2014 WF] Metal Processing Plant 题解 P7624 [AHOI2021初中组] 地铁题解 P7962 [NOIP2021] 方差题解 P8321 『JROI-4』沈阳大街 2 题解 P7315 [COCI 2018/2019 #3] Sajam 题解 P5621 [DBOI2019] 德丽莎世界第一可爱题解 P14224 [ICPC 2024 Kunming I] 子数组题解 CF720A Closing ceremony 题解 P14303 [GCJ 2011 Finals] Runs 加强版题解 P13382 [GCJ 2011 Finals] Runs 题解 SP3912 MTREECOL - Color a tree 题解 CF946E Largest Beautiful Number 题解 AT_agc003_e [AGC003E] Sequential operations on Sequence 题解 P5955 [POI 2018] Pionek 题解 P10671 BZOJ1278 向量 vector 题解 P12766 [POI 2018 R3] 完备数 Complete numbers 题解 P10664 BZOJ3328 PYXFIB 题解 P14185 回文子串划分计数题解 CF932G Palindrome Partition 题解 AT_abc230_g [ABC230G] GCD Permutation 题解 CF870E Points, Lines and Ready-made Titles 题解 P7561 [JOISC 2021] 道路の建設案 (Road Construction) (Day2) 题解 P14162 [ICPC 2022 Nanjing R] 完美匹配题解 P14154 [ICPC 2022 Nanjing R] 索道题解 P14153 [ICPC 2022 Nanjing R] 停停，昨日请不要再重现题解 P14159 [ICPC 2022 Nanjing R] 邪恶铭刻题解 P14156 [ICPC 2022 Nanjing R] 聊天程序题解 P14161 [ICPC 2022 Nanjing R] 完美回文题解 P14158 [ICPC 2022 Nanjing R] 三角形题解 P9849 [ICPC 2021 Nanjing R] Xingqiu's Joke 题解 P9847 [ICPC 2021 Nanjing R] Crystalfly 题解 CF794E Choosing Carrot 题解 P13509 [OOI 2024] Almost Certainly 题解 AT_arc116_f [ARC116F] Deque Game 题解 AT_agc029_b [AGC029B] Powers of two 题解 P4347 [CERC2015] Book Borders 题解 CF185D Visit of the Great 题解 P9841 [ICPC 2021 Nanjing R] Puzzle in Inazuma 题解 CF729F Financiers Game 题解 CF403D Beautiful Pairs of Numbers 题解 CF2133E I Yearned For The Mines 题解 CF1513E Cost Equilibrium 题解 CF317B Ants 题解 CF1789F Serval and Brain Power 题解 P6122 [NEERC 2016] Mole Tunnels 题解 CF1458D Flip and Reverse 题解 P13536 [IOI 2025] 神话三峰（triples）（Part 1）题解 P13271 [NOI2025] 机器人题解 AT_agc017_e [AGC017E] Jigsaw 题解 P5481 [BJOI2015] 糖果题解 P3805 【模板】Manacher 题解 P1943 Local Maxima 题解 CF830E Perpetual Motion Machine 题解 P3412 仓鼠找sugar II 题解 P11073 Game King 题解 CF1131G Most Dangerous Shark 题解 CF2089D Conditional Operators 题解 P12055 [THUPC 2025 决赛] 一个 01 串，n 次三目运算符，最后值为 1 题解 P3278 [SCOI2013] 多项式的运算题解 P3272 [SCOI2011] 地板题解 P12179 DerrickLo's Game (UBC002B) 题解 CF979E Kuro and Topological Parity 题解 CF1919D 01 Tree 题解 P4484 [BJWC2018] 最长上升子序列题解 AT_arc195_e [ARC195E] Random Tree Distance 题解 B4269 [朝阳区小学组 2019] square 题解 CF2091G Gleb and Boating 题解 P8456 「SWTR-8」地地铁铁题解 P11952 [科大国创杯初中组 2023] 行走题解 CF2081D MST in Modulo Graph 题解 CF1045C Hyperspace Highways 题解 P6335 [COCI 2007/2008 #1] STAZA 题解 AT_joisc2016_i 電報题解 CF2077B Finding OR Sum 题解 P3050 [USACO12MAR] Large Banner G 题解 P11856 [CSP-J 2022 山东] 吟诗题解 P11854 [CSP-J 2022 山东] 宴会题解 P11855 [CSP-J 2022 山东] 部署题解 CF804E The same permutation 题解 CF1420D Rescue Nibel! 题解 CF1996G Penacony 题解 CF1951E No Palindromes 题解 CF1815F OH NO1 (-2-3-4) 题解 CF1977E Tensor 题解 CF1943C Tree Compass 题解 CF837E Vasya's Function 题解 AT_arc149_c [ARC149C] Avoid Prime Sum 题解 CF629D Babaei and Birthday Cake 题解 CF1042F Leaf Sets 题解 CF97D Robot in Basement 题解 AT_arc193_a [ARC193A] Complement Interval Graph 题解 P11604 [PA 2016] 卡牌 / Gra w karty 题解 CF812E Sagheer and Apple Tree 题解 CF1310D Tourism 题解 CF1693C Keshi in Search of AmShZ 题解 CF1137B Camp Schedule 题解 CF1270E Divide Points 题解 CF1029E Tree with Small Distances 题解 CF1943B Non-Palindromic Substring 题解 CF446D DZY Loves Games 题解 CF1592F2 Alice and Recoloring 2 题解 CF1839E Decreasing Game 题解 CF1732D2 Balance (Hard version) 题解 CF1732D1 Balance (Easy version) 题解 CF1981D Turtle and Multiplication 题解 CF40E Number Table 题解 CF51E Pentagon 题解 CF732F Tourist Reform 题解 CF793C Mice problem 题解 CF126D Fibonacci Sums 题解 CF1705E Mark and Professor Koro 题解 CF425D Sereja and Squares 题解 CF300E Empire Strikes Back 题解 CF364C Beautiful Set 题解 CF898F Restoring the Expression 题解 CF908G New Year and Original Order 题解 CF460D Little Victor and Set 题解 CF895E Eyes Closed 题解 CF1967C Fenwick Tree 题解 CF607C Marbles 题解 CF1411E Poman Numbers 题解 CF1623D Robot Cleaner Revisit 题解 CF178F3 Representative Sampling 题解 CF1605D Treelabeling 题解 CF2056D Unique Median 题解 CF1983F array-value 题解 CF1238E Keyboard Purchase 题解 CF1553F Pairwise Modulo 题解 CF484B Maximum Value 题解 CF1470D Strange Housing 题解 CF1498E Two Houses 题解 CF1923E Count Paths 题解 CF2049E Broken Queries 题解 CF147B Smile House 题解 CF1712E1 LCM Sum (easy version) 题解 CF1646E Power Board 题解 AT_tdpc_tree 木题解 AT_tdpc_lexicographical 辞書順题解 CF2036G Library of Magic 题解 CF1834D Survey in Class 题解 CF1884D Counting Rhyme 题解 CF1886D Monocarp and the Set 题解 CF1617D1 Too Many Impostors (easy version) 题解 CF1780D Bit Guessing Game 题解 CF1804D Accommodation 题解 CF1796D Maximum Subarray 题解 CF2030B Minimise Oneness 题解 CF2030D QED's Favorite Permutation 题解 CF1731E Graph Cost 题解 CF1442C Graph Transpositions 题解 CF1165F1 Microtransactions (easy version) 题解 CF1165F2 Microtransactions (hard version) 题解 CF1481D AB Graph 题解 AT_joi2018ho_e 毒蛇の脱走 (Snake Escaping) 题解 P7670 [JOI 2018 Final] 毒蛇越狱 / Snake Escaping 题解 P7669 [JOI 2018 Final] 月票购买 / Commuter Pass 题解 AT_joi2018ho_d 定期券 (Commuter Pass) 题解 CF1358E Are You Fired? 题解 CF1453E Dog Snacks 题解 P11078 「FSLOI Round I」迷雾题解 P2998 [USACO10NOV] Candy S 题解 P10895 选择困难症题解 CF1619E MEX and Increments 题解 CF888D Almost Identity Permutations 题解 CF863E Turn Off The TV 题解

通过作差可以发现答案是一个 $k+1$ 次多项式的形式，因此想到 Lagrange 插值。将 $x_i=i$ （ $0\le i\le n$ ）带入，有：

\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}

后面这两个 $\prod$ 一看就很能预处理，而前面的显然可以直接算。时间复杂度为 $O(n\log n)$ 。注意到 $i^k$ 是积性函数，所以使用线性筛可以将其优化至严格 $O(n)$ 求解。

喜欢的话，留下你的评论吧～

随机文章

加载中...