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 浙江

孙梓航

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

啊，对对，我也这么做的

点赞回复分享

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

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

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

这么拜谢

点赞回复分享

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

slzx2022yyh

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

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

点赞回复分享

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

slzx2022yyh

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

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

点赞回复分享