还要变换多少次,才能遇到那个你

题目大意

给 $m$ 个数 $c_1, c_2, c_3, c_4…c_m$, 存在数列 $c_a,c_b,c_c, c_d…$ 使得和为 $n$

求不同排列的方案数 模 1005060097

数据范围

$30\%$ 数据 $n,m,c <= 5000$

$100\%$ 数据 $n,m,c <= 100000$

题解

首先我们认识一下,什么是 构造函数(母函数)

具体的定义呢,涉及到一系列的数学问题

在这里大致介绍一下它的用途,参考 母函数介绍

也就是说,我们根据题意可以构造出一个函数 $C = a_0x^0 + a_1x^1 + a_2x^2 + … + a_nx^n$ (只求到 $n$)$+ a_{n + 1} x^{n+1} + …$

其中 $a_i$ 表示 $i$ 在 $c$ 数组中出现了多少次, 即 只取一个数,有多少种不同的取到 $i$ 的方案

由此可以推得 $C^2$ 为取两个数时,有多少种不同的方法

我们要统计的答案,就是 $(ans) a_n = (C^1) a_n + (C^2) a_n + (C^3) a_n + … + (C^{\infty}) a_n$

考虑一下化简, $ans = \frac{1 - C^{\infty}}{1 - C}$, 想一下, $C^{\infty}$ 对答案没有影响, 所以 答案化简为 $\frac{1}{1 - C}$

好了,现在我们的问题明显了,求 $\frac{1}{1 - C}$ 在模 1005060097 意义下的多项式