题解：AT_abc241_h [ABC241Ex] Card Deck Score

ty_mxzhn · 2024-12-14 15:56:50 · 题解

先把 b_i 这个限制扔掉试试看。生成函数大家都会吧！答案即为 \displaystyle [x^m]\prod_{i=1}^n\dfrac{1}{1-a_ix}。

不容易想到的，考虑待定系数法。我们使得 \displaystyle \prod_{i=1}^n \dfrac{1}{1-a_ix}=\sum_{i=1}^n \dfrac{c_i}{1-a_ix}。

这个式子可以变成 \displaystyle \sum_{i=1}^n c_i\prod_{j\neq i}(1-a_jx)=1。基本的技巧是代入 \dfrac{1}{a_1},\dfrac{1}{a_2},\dots,\dfrac{1}{a_n}。 则有 \displaystyle c_i\prod_{j\neq i}(1-\dfrac{a_j}{a_i})=1。有点像拉格朗日插值。

至此我们可以在 O(n^2) 的时间内解决 c_i 的问题。接下来答案即为 \displaystyle \sum_{i=1}^nc_ia_i^m。

剩下的部分都不难了。考虑硬币购物式的容斥，则枚举一个集合 S 超过限制，这是容易计算的。

时间复杂度 O(n^2+n2^n\log p)。