还要变换多少次,才能遇到那个你
题目大意
给 $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 意义下的多项式