2023-10-10 22:38 已编辑慈溪市上林初级中学课程设计发布于浙江

关注

2023牛客OI赛前集训营-提高组（第四场）T3 加法方案题解

加法方案

https://ac.nowcoder.com/acm/contest/65195/C

T3 加法方案题解

官方题解里面有一个毒瘤的 NTT，这里讲一下如何与多项式保持安全距离。

首先为了处理方便，可以给所有情况中再加上一种 $n 0 = n$ ，现在所有情况两两对应（所有 $x y = s$ 的情况都可以对应一种 $y x = s$ 的情况）。

考虑每一位造成的贡献。

设从低到高第 $i$ 位为 $a_{i - 1}$ ，最终凑出的两个数分别为 $x$ 和 $y$ 。

考虑枚举 $a_i$ 前面有 $j$ 个数放进了 $x$ ，我们强制 $a_i$ 放入 $x$ （ $a_i$ 放入 $y$ 的贡献只要再乘 $2$ 即可），则只考虑从低到高的前 $i 1$ 位， $a_i$ 的贡献为 $a_i \cdot \sum_{j = 0}^{i} 10^j \cdot C_{i}^{j} = a_i \cdot \sum_{j = 0}^{i} 10^j \cdot 1^{i - j} \cdot C_{i}^{j} = a_i \cdot (10 1)^{i} = a_i \cdot 11^i$ 。

再考虑 $a_i$ 后面的高位的情况。每位都有 $2$ 种情况，放入 $x$ 或放入 $y$ ，并且不会对 $a_i$ 造成影响。因此 $a_i$ 的贡献为 $a_i \cdot 11^i \cdot 2^{m - 1 - i}$ 。

设求出的 $a_i$ 的贡献之和为 $ans$ ，则最终答案为 $2ans - n$ 。（因为原来只求出了 $a_i$ 放入 $x$ 的贡献，同时 $n$ 被算了两遍）

全部评论

推荐最新楼层

slzx2022yyh

慈溪市上林初级中学教育集团 iOS开发

还有那个101应该是10+1吧

1 回复分享

发布于 2023-10-10 22:43 浙江

slzx2022yyh

慈溪市上林初级中学教育集团 iOS开发

考场上没想到数学式子的化简，%%%%%rp%%%%%

点赞回复分享

发布于 2023-10-10 22:42 浙江

slzx2022yyh

慈溪市上林初级中学教育集团 iOS开发

所以我多项式系数在学些什么！

点赞回复分享

发布于 2023-10-10 22:43 浙江

我祈祷拥有一颗透明的心灵和会流泪的眼睛

夜空中最亮的星能否听清那仰望的人心底的孤独和叹息 oh夜空中最亮的星能否记起曾与我同行消失在风里的身影我祈祷拥有一颗透明的心灵和会流泪的眼睛给我再去相信的勇气 oh越过谎言去拥抱你每当我找不到存在的意义每当我迷失在黑夜里 oh~夜空中最亮的星请指引我靠近你夜空中最亮的星是否知道曾与我同行的身影如今在哪里 oh夜空中最亮的星是否在意是等太阳升起还是意外先来临我宁愿所有痛苦都留在心里也不愿忘记你的眼睛给我再去相信的勇气 oh越过谎言去拥抱你每当我找不到存在的意义每当我迷失在黑夜里 oh~夜空中最亮的星 oh请照亮我前行我祈祷拥有一颗透明的心灵和会流泪的眼睛给我再去相信的勇气 oh越过谎言去拥抱你每当我找不到存在的意义每当我迷失在黑夜里 oh~夜空中最亮的星 oh请照亮我前行夜空中最亮的星能否听清那仰望的人心底的孤独和叹息临床研究

这么拜谢

点赞回复分享

发布于 2023-10-11 07:45 日本

孙梓航

慈溪市上林初级中学教育集团前端工程师

啊，对对，我也这么做的

点赞回复分享

发布于 2023-10-11 12:43 浙江

11-27 17:08

已编辑

牛客_产品运营部_私域运营

解码！2025届校招白菜、sp、ssp薪资档位公开！

腾讯普通offer 24k～26k * 15，年包在36w～39w左右。

点赞评论收藏

不愿透露姓名的神秘牛友

11-29 12:24

美团工作体验

福利上，网上的传言有点夸张，实际上还是有一些福利的，有不少活动可以参加。团队氛围超级好，大家都很友善，问什么问题都有人耐心回答，导师人很好，而且我的领导也特别关心我，会问我生活上有没有困难，需不需要帮助，或者有什么疑问。工作上也没有太大的压力，领导会给一些发展方向的建议，在这里能慢慢找到自己的节奏。

美团公司氛围 1908人发布

点赞评论收藏

10-27 17:26

东北大学 Java

26届，想找日常实习，求拷打

简历放在这了😋

从来不奋斗：项目也太典了

点赞评论收藏

11-29 14:47

字节跳动_后端开发(准入职员工)

逆天华为

逆天 hr。。先是在面试之前给我换了两次面试时间，面试完就不回消息了。面试时候我已经明确说了我不接受上海和深圳，没有 hc 你给我挂了就是了现在说这个😅化身华黑子，纯逆天

沉淀一会：1.同学你面试评价不错，概率很大，请耐心等待； 2.你的排名比较靠前，不要担心，耐心等待； 3.问题不大，正在审批，不要着急签其他公司，等等我们！ 4.预计9月中下旬，安心过节； 5.下周会有结果，请耐心等待下； 6.可能国庆节前后，一有结果我马上通知你； 7.预计10月中旬，再坚持一下； 8.正在走流程，就这两天了； 9.同学，结果我也不知道，你如果查到了也告诉我一声； 10.同学你出线不明朗，建议签其他公司保底！ 11.同学你找了哪些公司，我也在找工作。

点赞评论收藏