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$ 被算了两遍）

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

T3 加法方案 题解

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

T3 加法方案题解