打卡信奥刷题（3125）用C++实现信奥题 P7419 「PMOI-2」参天大树

张开发
• 2026/4/17 23:08:50 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

打卡信奥刷题（3125）用C++实现信奥题 P7419 「PMOI-2」参天大树
P7419 「PMOI-2」参天大树题目描述b6e0 有一棵参天大树。这棵二叉有根树有无数多个节点。它的根节点的编号为111对于每一个x(x≥1)x(x\ge1)x(x≥1)编号为xxx的节点有编号为2x2x2x和2x12x12x1的子节点。你需要在编号小于等于nnn的节点中选出两个可以相同的节点求出所有情况中它们的最近公共祖先的编号的和。也就是求其中LCA⁡(i,j)\operatorname{LCA}(i,j)LCA(i,j)表示iii与jjj的最近公共祖先的编号∑i1n∑j1nLCA⁡(i,j)\sum_{i1}^n\sum_{j1}^n \operatorname{LCA}(i,j)i1∑n​j1∑n​LCA(i,j)保证存在一个自然数kkk满足n2k−1n2^k-1n2k−1。答案对998244353998244353998244353取模。输入格式本题有多组询问。第一行一个正整数ttt表示询问的次数。下面ttt行每行一个自然数kkk表示第iii次询问的n2k−1n2^k-1n2k−1。输出格式输出ttt行第iii行表示第iii次询问的答案对998244353998244353998244353取模的值。输入输出样例 #1输入 #12 2 3输出 #112 88说明/提示【样例解释】对于第一次询问n22−13n2^2-13n22−13答案为111121113121111211131211112111312。【数据范围】本题采用捆绑测试。Subtask120ptsk≤8k\le8k≤8Subtask220ptst,k≤300t,k\le300t,k≤300Subtask320ptsk≤104k\le10^4k≤104Subtask440pts无特殊限制。对于100%100\%100%的数据1≤t,k≤1061\le t,k\le10^61≤t,k≤106。C实现#includebits/stdc.husingnamespacestd;#definelllonglongll mod998244353;ll f[1000006];intmain(){f[1]1;ll siz1;for(inti2;i1000000;i){f[i]((f[i-1]2)((siz*siz)1)siz*siz(siz2)1)%mod;siz((siz1)1)%mod;}intT;cinT;ll k;while(T--){scanf(%lld,k);printf(%lld\n,f[k]);}}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容

更多文章