2023牛客OI赛前集训营-提高组（第四场）T3 加法方案 题解
加法方案
https://ac.nowcoder.com/acm/contest/65195/C
T3 加法方案 题解
官方题解里面有一个毒瘤的 NTT，这里讲一下如何与多项式保持安全距离。
首先为了处理方便，可以给所有情况中再加上一种 ，现在所有情况两两对应（所有
的情况都可以对应一种
的情况）。
考虑每一位造成的贡献。
设从低到高第 位为
，最终凑出的两个数分别为
和
。
考虑枚举 前面有
个数放进了
，我们强制
放入
（
放入
的贡献只要再乘
即可），则只考虑从低到高的前
位，
的贡献为
。
再考虑 后面的高位的情况。每位都有
种情况，放入
或放入
，并且不会对
造成影响。因此
的贡献为
。
设求出的 的贡献之和为
，则最终答案为
。（因为原来只求出了
放入
的贡献，同时
被算了两遍）
查看5道真题和解析
投递美团等公司10个岗位 >
