「AHU 2023 校赛 J」沉默乐团

防 AK 题。只可惜多项式技巧不够炉火纯青，差一点就把柿子推出来了。

所以说爱妈题面呢搞快点 /se

传送门

或者说这里还有一份形式化题面：

给定 $n, m, k$ 和 $a, b \in (\mathbb Z_p / \{0\})^n$。令

$$t_i = ([1, a_i] \cap \mathbb Z)^{b_i}$$ $$T = \prod_{i = 1}^n t_i$$ $$f(x) = \sum_{s \in T} \left[\sum_{v \in s} [v \geqslant k] = x\right]$$

试求 $f(0), f(1), \dots, f(m)$ 的值。对 $998244353$ 取模。

应该没有写错吧……

首先忽略所有 $a_i \lt k$ 的演奏家。这部分的贡献是很容易计算的。

以下只考虑 $a_i \geqslant k$ 的情况。

我们可以容易地写出第 $i$ 位演奏家的一次演奏的生成函数

$$(a_i - k + 1)x + (k - 1)$$

那么第 $i$ 位演奏家的生成函数就是

$$((a_i - k + 1)x + (k - 1))^{b_i}$$

总体的生成函数就是

$$\prod_{i = 1}^n ((a_i - k + 1)x + (k - 1))^{b_i}$$

于是开始推柿子

$$\begin{aligned} & \prod_{i = 1}^n ((a_i - k + 1) x + (k - 1))^{b_i} \\ = & \prod_{i = 1}^n (k - 1)^{b_i} \prod_{i = 1}^n \left(1 + \frac{a_i - k + 1}{k - 1} x\right)^{b_i} \\ = & \prod_{i = 1}^n (k - 1)^{b_i} \exp \sum_{i = 1}^n b_i \ln \left(1 + \frac{a_i - k + 1}{k - 1} x\right) \\ = & \prod_{i = 1}^n (k - 1)^{b_i} \exp \sum_{i = 1}^n b_i \sum_{j \geqslant 1} \frac{(-1)^{j - 1} \left(\frac{a_i - k + 1}{k - 1}\right)^j x^j}{j} \\ = & \prod_{i = 1}^n (k - 1)^{b_i} \exp \sum_{j \geqslant 1} \frac{(-1)^{j - 1} x^j}{j} \sum_{i = 1}^n b_i \left(\frac{a_i - k + 1}{k - 1}\right)^j \end{aligned}$$

注意到里面有一个 $\sum x^j \sum b_i d_i^j$ 的形式。这个该怎么处理呢？

$$\begin{aligned} & \sum_{j \geqslant 0} x^j \sum_{i = 1}^n b_i d_i^j \\ = & \sum_{i = 1}^n b_i \sum_{j \geqslant 0} (d_i x)^j \\ = & \sum_{i = 1}^n \frac{b_i}{1 - d_i x} \\ = & \frac{\sum_{i = 1}^n b_i \prod_{j \neq i}(1 - d_i x)}{\prod_{i = 1}^n (1 - d_i x)} \end{aligned}$$

总结：菜就多刷题。