普通生成函数

引入

生成函数（generating function），又称母函数，是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息，是解决排列组合问题的有力工具。

Q: 什么叫做形式幂级数？
A: 若某个生成函数为 \(F(x) = \sum a_n x^n\)，那么其中的 \(x\) 对其取值范围并不是重点，其充当形式参数，没有实际意义，所以我们也不关心敛散性，而 \(a_n\) 才是我们需关注的重点。

本文主要探讨的是普通生成函数（ordinary generating function，OGF）。

前置知识

如下符号需要先感知：

\([x^i]f(x)\)

表示多项式 \(f(x)\) 在 \(x^i\) 处的系数
若其中的一项为 \(2023x^3\)，那么 \([x^3]f(x) = 2023\)

下降幂

\(x\) 的 \(n\) 阶下降幂为 \(x^{\underline{n}} = x(x - 1)\cdots(x - n + 1)\)
组合数的分子也恰好为这个形式

\(\dbinom{n}{i}\)

即组合数 \(C_n^i\)
有的地方也写为下降幂的形式，即 \(\frac{n^{\underline{i}}}{i!}\)

\(\sum_{i \geq 0}\)

等价于 \(\sum_{i=0}^{\infty}\)，这类求和默认右边无穷，数均为整数

如下定理需要先感知：

二项式定理

\((x + y)^n = \sum_{i=0}^n \dbinom{n}{i} x^{n - i} y^i\)，其中 \(\dbinom{n}{i} = \frac{n!}{i!(n - i)!}\) 是组合数。

广义二项式定理

\((x + y)^{\alpha} = \sum_{i=0}^{\infty} \dbinom{\alpha}{i} x^{\alpha - i} y^i\)

其中 \(\alpha\) 可以为一切实数，也就是说其可以为负数和浮点数
其中 \(\dbinom{\alpha}{i} = \frac{\alpha^{\underline{i}}}{i!} = \frac{\alpha(\alpha - 1)(\alpha - 2)\cdots(\alpha - i + 1)}{i!}\)，可以理解为在实数域上的组合数。

定义

序列 \(a\) 的普通生成函数（ordinary generating function，OGF）定义为形式幂级数：

\[ F(x)=\sum_{n}a_n x^n \]

\(a\) 既可以是有穷序列，也可以是无穷序列。常见的例子（假设 \(a\) 以 \(0\) 为起点）：

序列 \(a=\langle 1,2,3\rangle\) 的普通生成函数是 \(1+2x+3x^2\)。
序列 \(a=\langle 1,1,1,\cdots\rangle\) 的普通生成函数是 \(\sum_{n\ge 0}x^n\)。
序列 \(a=\langle 1,2,4,8,16,\cdots\rangle\) 的生成函数是 \(\sum_{n\ge 0}2^nx^n\)。
序列 \(a=\langle 1,3,5,7,9,\cdots\rangle\) 的生成函数是 \(\sum_{n\ge 0}(2n+1)x^n\)。

换句话说，如果序列 \(a\) 有通项公式，那么它的普通生成函数的系数就是通项公式。

普通生成函数的基本运算

考虑两个序列 \(a,b\) 的普通生成函数，分别为 \(F(x),G(x)\)。那么有

\[ F(x)\pm G(x)=\sum_n (a_n\pm b_n)x^n \]

因此 \(F(x)\pm G(x)\) 是序列 \(\langle a_n\pm b_n\rangle\) 的普通生成函数。

考虑乘法运算，也就是卷积：

\[ F(x)G(x)=\sum_n x^n \sum_{i=0}^na_ib_{n-i} \]

因此 \(F(x)G(x)\) 是序列 \(\langle \sum_{i=0}^n a_ib_{n-i} \rangle\) 的普通生成函数。

封闭形式

在运用生成函数的过程中，我们不会一直使用形式幂级数的形式，而会适时地转化为封闭形式以更好地化简。

例如 \(\langle 1,1,1,\cdots\rangle\) 的普通生成函数 \(F(x)=\sum_{n\ge 0}x^n\)，我们可以发现

\[ F(x)x+1=F(x) \]

那么解这个方程得到

\[ F(x)=\frac{1}{1-x} \]

这就是 \(\sum_{n\ge 0}x^n\) 的封闭形式。

考虑等比数列 \(\langle 1,p,p^2,p^3,p^4,\cdots\rangle\) 的生成函数 \(F(x)=\sum_{n\ge 0}p^nx^n\)，有

\[ \begin{aligned}F(x)px+1 &=F(x)\\F(x) &=\frac{1}{1-px}\end{aligned} \]

等比数列的封闭形式与展开形式是常用的变换手段。

小练习

请求出下列数列的普通生成函数（形式幂级数形式和封闭形式）。难度是循序渐进的。

\(a=\langle 0,1,1,1,1,\cdots\rangle\)。
\(a=\langle 1,0,1,0,1,\cdots \rangle\)。
\(a=\langle 1,2,3,4,\cdots \rangle\)。
\(a_n=\binom{m}{n}\)（ \(m\) 是常数，\(n\ge 0\)）。
\(a_n=\binom{m+n}{n}\)（ \(m\) 是常数，\(n\ge 0\)）。

答案

第一个：

\[ F(x)=\sum_{n\ge 1}x^n=\frac{x}{1-x} \]

第二个：

\[ \begin{aligned} F(x)&=\sum_{n\ge 0}x^{2n}\\ &=\sum_{n\ge 0}(x^2)^{n}\\ &=\frac{1}{1-x^2} \end{aligned} \]

第三个（求导）：

\[ \begin{aligned}F(x)&=\sum_{n\ge 0}(n+1)x^n\\&=\sum_{n\ge 1}nx^{n-1}\\&=\sum_{n\ge 0}(x^n)'\\&=\left(\frac{1}{1-x}\right)'\\&=\frac{1}{(1-x)^2}\end{aligned} \]

第四个（二项式定理）：

\[ F(x)=\sum_{n\ge 0}\binom{m}{n}x^n=(1+x)^m \]

第五个：

\[ F(x)=\sum_{n\ge 0}\binom{m+n}{n}x^n=\frac{1}{(1-x)^{m+1}} \]

可以使用归纳法证明。

首先当 \(m=0\) 时，有 \(F(x)=\frac{1}{1-x}\)。

而当 \(m \geq 0\) 时，有

\[ \begin{aligned} \frac{1}{(1-x)^{m+1}} &=\frac{1}{(1-x)^m}\frac{1}{1-x}\\ &=\left(\sum_{n\ge 0}\binom{m+n-1}{n}x^n \right)\left(\sum_{n\ge 0}x^n \right)\\ &=\sum_{n\ge 0} x^n\sum_{i=0}^n \binom{m+i-1}{i}\\ &=\sum_{n\ge 0}\binom{m+n}{n}x^n \end{aligned} \]

斐波那契数列的生成函数

接下来我们来推导斐波那契数列的生成函数。

斐波那契数列定义为 \(a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}\;(n>1)\)。设它的普通生成函数是 \(F(x)\)，那么根据它的递推式，我们可以类似地列出关于 \(F(x)\) 的方程：

\[ F(x)=xF(x)+x^2F(x)-a_0x+a_1x+a_0 \]

那么解得

\[ F(x)=\frac{x}{1-x-x^2} \]

那么接下来的问题是，如何求出它的展开形式？

展开方式一

不妨将 \(x+x^2\) 当作一个整体，那么可以得到

\[ \begin{aligned} F(x)&=\frac{x}{1-(x+x^2)}\\ &=\sum_{n\ge 0}(x+x^2)^n\\ &=\sum_{n\ge 0}\sum_{i=0}^n\binom{n}{i}x^{2i}x^{n-i}\\ &=\sum_{n\ge 0}\sum_{i=0}^n\binom{n}{i}x^{n+i}\\ &=\sum_{n\ge 0}x^n\sum_{i=0}^n\binom{n-i}{i} \end{aligned} \]

我们得到了 \(a_n\) 的通项公式，但那并不是我们熟知的有关黄金分割比的形式。

展开方式二

考虑求解一个待定系数的方程：

\[ \frac{A}{1-ax}+\frac{B}{1-bx}= \frac{x}{1-x-x^2} \]

通分得到

\[ \frac{A-Abx+B-aBx}{(1-ax)(1-bx)} = \frac{x}{1-x-x^2} \]

待定项系数相等，我们得到

\[ \begin{cases} A+B=0\\ -Ab-aB=1\\ a+b=1\\ ab=-1 \end{cases} \]

解得

\[ \begin{cases} A=\frac{1}{\sqrt{5}}\\ B=-\frac{1}{\sqrt{5}}\\ a=\frac{1+\sqrt{5}}{2}\\ b=\frac{1-\sqrt{5}}{2} \end{cases} \]

那么我们根据等比数列的展开式，就可以得到斐波那契数列的通项公式：

\[ \frac{x}{1-x-x^2}=\sum_{n\ge 0}x^n \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n \right) \]

这也被称为斐波那契数列的另一个封闭形式（\(\frac{x}{1-x-x^2}\) 是一个封闭形式）。

对于任意多项式 \(P(x),Q(x)\)，生成函数 \(\frac{P(x)}{Q(x)}\) 的展开式都可以使用上述方法求出。在实际运用的过程中，我们往往先求出 \(Q(x)\) 的根，把分母表示为 \(\prod (1-p_ix)^{d_i}\) 的形式，然后再求分子。

当对分母进行因式分解但有重根时，每有一个重根就要多一个分式，如考虑生成函数

\[ G(x)=\frac{1}{(1-x)(1-2x)^2} \]

的系数的通项公式，那么有

\[ G(x)=\frac{c_0}{1-x}+\frac{c_1}{1-2x}+\frac{c_2}{(1-2x)^2} \]

解得

\[ \begin{cases} c_0&=1\\ c_1&=-2\\ c_2&=2 \end{cases} \]

那么

\[ [x^n]G(x)=1-2^{n+1}+(n+1)\cdot 2^{n+1} \]

普通生成函数的组合意义

砝码称重

假设质量为 \(1\) 克、\(2\) 克、\(3\) 克、\(4\) 克的砝码各一枚，能称出哪些重量？每种重量各有几种方案？

约定：形式参数 \(x^i\) 表示取了 \(i\) 克的物品。

为了方便陈述，对于某一类砝码我们设辅助序列 \(a\)，若重量 \(i\) 克能取到，则 \(a_i = 1\)，否则为0。

对于 \(1\) 克砝码的下标从 \(0\) 开始。
选取 \(1\) 克砝码，不取时为 \(0\) 克，取时为 \(1\) 克，故序列 \(a = \langle 1, 1, 0, 0, 0, \cdots, 0 \rangle\)，故该砝码选取的方案的GF（生成函数）为 \(1x^0 + 1x^1 + 0x^2 + \cdots + \cdots + 0x^{\infty}\)，因为后面系数全是 \(0\)，故其选取方案即表示为 \((1 + x^1)\)，GF即表示为 \((1 + x^1)\)
同理，\(2\) 克砝码取方案，故序列 \(a = \langle 1, 0, 1, 0, 0, 0, \cdots \rangle\)，GF即表示为 \((1 + x^2)\)
同理，\(3\) 克砝码取方案，故序列 \(a = \langle 1, 0, 0, 1, 0, 0, \cdots \rangle\)，GF即表示为 \((1 + x^3)\)
同理，\(4\) 克砝码取方案，即表示为 \((1 + x^4)\)

故总的生成函数为：

\(F(x) = (1 + x^1)(1 + x^2)(1 + x^3)(1 + x^4)\)

\(= 1 + x + x^2 + 2x^3 + 2x^4 + 2x^5 + 2x^6 + 2x^7 + x^8 + x^9 + x^{10}\)

每个 \(x^i\) 前面的系数，即是他们的方案数

不取、取 \(1\) 克、取 \(8\) 克、取 \(9\) 克、取 \(10\) 克： \(1\) 种方案
取 \(2\) 克、取 \(3\) 克、取 \(4\) 克、取 \(5\) 克、取 \(6\) 克、取 \(7\) 克： \(2\) 种方案

拓展1：若每个砝码的数量改为 \(a_k\) 呢？

根据上面的思路，不难拓展，只需要修改每一类砝码所对应的 \(a\) 数组，即可得到其对应的GF
若对于四个 \(3\) 克砝码，其GF即为 \((1 + x^3 + x^6 + x^9 + x^{12})\)

拓展2：若我们想知道具体用哪几种砝码该怎么办？

原本GF（生成函数）的一项的表示形式为 \(a_i x^i\)，表示取 \(i\) 克的砝码有 \(a_i\) 种方案
我们将每个砝码的选取的表示，变换为： \(y_j^{k} \times x^i\)，表示取 \(i\) 克的砝码，需要使用质量为 \(j\) 克的砝码 \(k\) 个
如，对于一个 \(2\) 克砝码来说，就是 \((1 + y_2^1 x^2)\)
如，对于两个 \(3\) 克砝码来说，就是 \((1 + y_3^1 x^3 + y_3^2 x^6)\)

最后的GF中 \(x^i\) 前面的系数就会形如 \((y_1^{k_1} y_2^{k_2} y_3^{k_3} + \cdots)\) 的形式，我们也就可以通过其中的一项得出具体方案，如 \(2\) 克的砝码取 \(k_4\) 个即可。

取球问题

假设有 \(n\) 个箱子，所有箱子里的球都相同，第 \(i\) 个箱子里面有 \(b_i\) 个球，求解拿取 \(1 \sim \sum_{i=1}^n b_i\) 个球分别有多少种方案？

约定：形式参数 \(x^i\) 表示取了 \(i\) 个球。

我们同样约定辅助序列 \(a\)，若能取到 \(i\) 个球，则 \(a_i = 1\)，否则为0

对于第 \(1\) 个箱子，容易得到：当 \(j \in [0, b_1]\) 时，\(a_j = 1\)；当 \(j > b_1\) 时，\(a_j = 0\)，故其GF为 \((1 + x + x^2 + \cdots + x^{b_1})\)
同理，对于第 \(k\) 个箱子，其GF为 \((1 + x + x^2 + \cdots + x^{b_k})\)。

故总的GF为：

\(F(x) = (1 + x + x^2 + \cdots + x^{b_1})(1 + x + x^2 + \cdots + x^{b_2}) \cdots (1 + x + x^2 + \cdots + x^{b_n})\)

P10780 BZOJ3028 食物

明明这次又要出去旅游了，和上次不同的是，他这次要去宇宙探险！我们暂且不讨论他有多么 NC，他又幻想了他应该带一些什么东西。理所当然的，你当然要帮他计算携带 \(n\) 件物品的方案数。

他这次又准备带一些受欢迎的食物，如：蜜桃多啦，鸡块啦，承德汉堡等等。

当然，他又有一些稀奇古怪的限制：

每种食物的限制如下：

承德汉堡：偶数个；
可乐： \(0\) 个或 \(1\) 个；
鸡腿： \(0\) 个，\(1\) 个或 \(2\) 个；
蜜桃多：奇数个；
鸡块： \(4\) 的倍数个；
包子： \(0\) 个，\(1\) 个，\(2\) 个或 \(3\) 个；
土豆片炒肉：不超过一个；
面包： \(3\) 的倍数个；

注意，这里我们懒得考虑明明对于带的食物该怎么搭配着吃，也认为每种食物都是以『个』为单位（反正是幻想嘛），只要总数加起来是 \(n\) 就算一种方案。因此，对于给出的 \(n\)，你需要计算出方案数，并对 \(10007\) 取模。

对于所有数据，\(1\leq n\leq 10^{500}\)；

这是一道经典的生成函数题。对于一种食物，我们可以设 \(a_n\) 表示这种食物选 \(n\) 个的方案数，并求出它的生成函数。而两种食物一共选 \(n\) 个的方案数的生成函数，就是它们生成函数的卷积。多种食物选 \(n\) 个的方案数的生成函数也是它们生成函数的卷积。

在理解了方案数可以用卷积表示以后，我们就可以构造生成函数（标号对应题目中食物的标号）：

\(\displaystyle\sum_{n\ge 0}x^{2n}=\frac{1}{1-x^2}\)。
\(1+x\)。
\(1+x+x^2=\frac{1-x^3}{1-x}\)。
\(\frac{x}{1-x^2}\)。
\(\displaystyle \sum_{n\ge 0}x^{4n}=\frac{1}{1-x^4}\)。
\(1+x+x^2+x^3=\frac{1-x^4}{1-x}\)。
\(1+x\)。
\(\frac{1}{1-x^3}\)。

那么全部乘起来，得到答案的生成函数：

\[ F(x)=\frac{(1+x)(1-x^3)x(1-x^4)(1+x)}{(1-x^2)(1-x)(1-x^2)(1-x^4)(1-x)(1-x^3)} =\frac{x}{(1-x)^4} \]

然后我们将这个东西展开，你可以广义二项式定理，当然也可以直接展开。但是直接展开太麻烦了，我们还是广义二项式定理吧：

\[ \begin{aligned} \frac{x}{(x-1)^4} &= x(x-1)^{-4} \\ &= x\sum_{k=0}^{+\infty} \binom{-4}{k} x^k (-1)^{-4 -k} \\ &= x\sum_{k=0}^{+\infty} (-1)^k \binom{k+3}{k} x^k (-1)^{-4 -k} \\ &= x\sum_{k=0}^{+\infty} \binom{k+3}{k} x^k \\ &= \sum_{k=1}^{+\infty} \binom{k+2}{k-1} x^k \\ &= \sum_{k=1}^{+\infty} \frac{1}{6} k(k+1)(k+2) x^k \end{aligned} \]

所以答案就是 \(\frac{1}{6}k(k+1)(k+2)\)。

注意需要边读入边取模。

实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p = 10007, inv6 = 1668;
ll n;
char ch;
int main()
{
    while (isdigit(ch = getchar())) n = (n * 10 + ch - '0') % p;
    cout << ((n + 1) * (n + 2) * n * inv6) % p;
    return 0;
}

P4451 [国家集训队] 整数的lqp拆分

lqp在为出题而烦恼，他完全没有头绪，好烦啊…

他首先想到了整数拆分。整数拆分是个很有趣的问题。给你一个正整数 \(N\) ，对于N的一个整数拆分就是满足任意 \(m \geq 0\)， \(a_1 ,a_2 ,a_3…a_m \geq 0\)，且 \(a_1+a_2+a_3+…+a_m=n\) 的一个有序集合。通过长时间的研究我们发现了计算对于 \(n\) 的整数拆分的总数有一个很简单的递推式，但是因为这个递推式实在太简单了，如果出这样的题目，大家会对比赛毫无兴趣的。

然后 lqp 又想到了斐波那契数。定义 \(F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2} (n>1)\)， \(F_n\) 就是斐波那契数的第 \(n\) 项。但是求出第 \(n\) 项斐波那契数似乎也不怎么困难…

lqp 为了增加选手们比赛的欲望，于是绞尽脑汁，想出了一个有趣的整数拆分，我们暂且叫它：整数的lqp拆分。

和一般的整数拆分一样，整数的 lqp 拆分是满足任意 \(m \geq 0\)， \(a_1 ,a_2 ,a_3…a_m \geq 0\)，且 \(a_1+a_2+a_3+…+a_m=n\) 的一个有序集合。但是整数的lqp拆分要求的不是拆分总数，相对更加困难一些。

对于每个拆分，lqp 定义这个拆分的权值 \(F_{a_1}F_{a_2}…F_{a_m}\)，他想知道对于所有的拆分，他们的权值之和是多少？

简单来说，就是求

\(\sum\prod_{i=1}^m F_{a_i}\)

\(m \geq 0\)

\(a_1,a_2...a_m \geq 0\)

\(a_1+a_2+...+a_m=n\)

由于答案可能非常大，所以要对 \(10^9 + 7\) 取模。

【数据范围】对于 \(100\%\) 的数据，\(1\le n \le 10^{10000}\)。

首先考虑 Fibonacci 数的生成函数

\[ F(x) = \frac{x}{1 - x - x^2} \]

我们知道拆分为恰好 \(k\) 个数时，答案的生成函数为 \(F(x)^k\)，那么答案的生成函数显然为

\[ \begin{aligned} G(x) &= \sum_{i=0}^\infty F(x)^i \\ &= \frac{1}{1 - F(x)} \\ &= \frac{1 - x - x^2}{1 - 2x - x^2} \end{aligned} \]

分母写成递推式就是

\[ a_n = 2a_{n-1} + a_{n-2} \]

乘上分子得到答案

\[ \text{ans} = a_n - a_{n-1} - a_{n-2} = a_{n-1} \]

解递推式特征方程，得

\[ x_1 = -\sqrt{2} + 1, \quad x_2 = \sqrt{2} + 1 \]

设通项公式为

\[ a_n = c_1(-\sqrt{2} + 1)^n + c_2(\sqrt{2} + 1)^n \]

分别代入 \(n = 0, n = 1\)，解得

\[ \begin{cases} c_1 = \frac{\sqrt{2} - 1}{2\sqrt{2}} \\ c_2 = \frac{\sqrt{2} + 1}{2\sqrt{2}} \end{cases} \]

注意到 \(\sqrt{2}\) 在模 \(10^9 + 7\) 下存在（\(59713601\)），最终答案就出来了

\[ a_n \equiv 485071604 \times 940286408^n + 514928404 \times 59713601^n \pmod{10^9 + 7} \]

直接计算即可。

实现

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const ll p = 1e9 + 7, x = 485071604, y = 940286408, a = 514928404, b = 59713601;
ll qpow(ll a, ll b)
{
    static ll res;
    for (res = 1; b; b >>= 1, a = a * a % p)
        if (b & 1) res = res * a % p;
    return res;
}
ll read()
{
    static ll x;
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    for (x = 0; isdigit(ch); ch = getchar()) x = (x * 10 + ch - '0') % (p - 1);
    return x;
}
ll n;
int main()
{
    n = read() - 1;
    cout << (x * qpow(y, n) % p + a * qpow(b, n) % p) % p;
    return 0;
}

P4389 付公主的背包

付公主有一个背包

这个背包最多可以装 \(10^5\) 大小的东西

付公主有 \(n\) 种商品，她要准备出摊了

每种商品体积为 \(v_i\)，都有无限件

给定 \(m\)，对于 \(s\in [1,m]\)，请你回答用这些商品恰好装 \(s\) 体积的方案数

对于 \(100\%\) 的数据， \(1\le n,m \le 10^5\)， \(1\le v_i \le m\)。

每个物品的个数为无限，那么对于一个体积为 \(V\) 的物品，我们可以直接构建生成函数。

\[A(x) = \sum_{i=0}^{\infty} [i \% V = 0]x^i = \frac{1}{1 - x^V}\]

显然答案就是 \(m\) 个生成函数的卷积。

如果直接做答案是 \(O(mn \log n)\)，显然不是正确的复杂度。

我们看看怎么优化。生成函数除了形式幂级数的形式还有封闭形式，在 \(A(x)\) 后面已写出封闭形式，所以只需要把封闭形式的卷积求出来，然后求逆还原多项式。但这样复杂度是 \(O(2^m)\)，还是不行。

我们考虑把乘法化简，自然想到取对数变成加法。多项式求 \(\ln\) 复杂度是 \(O(n \log n)\)，但我们的多项式特殊，有：

\[\ln(1 - x^V) = - \sum_{i \geq 1} \frac{x^{Vi}}{i}\]

推导如下：设 \(\ln F(x) = G(x)\)，则

\[\begin{aligned} \frac{F'(x)}{F(x)} &= G'(x) \\ \frac{-Vx^{V - 1}}{1 - x^V} &= G'(x) \\ \sum_{i \geq 0} Vx^{V - 1 + Vi} &= G'(x) \\ \sum_{i \geq 0} \frac{Vx^{V + Vi}}{V + Vi} &= G(x) \\ \sum_{i \geq 1} \frac{x^{Vi}}{i} &= G(x) \\ \end{aligned}\]

于是，统计每一个容量的物品个数，然后 \(O(m / V)\) 给对应位置加上系数，总复杂度是 \(O(n \log n)\)。做完这步相当于给每个封闭形式 \(\ln\) 后求和。直接多项式 \(\exp\) 再多项式求逆后还原多项式，输出答案即可。

实现

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int MAXN = 4e5 + 10;
const ll p = 998244353, g = 3;
ll qpow(ll a, ll b)
{
    static ll res;
    for (res = 1; b; b >>= 1, a = a * a % p)
        if (b & 1) res = res * a % p;
    return res;
}
ll getinv(ll x) { return qpow(x, p - 2); }
const ll gi = getinv(g);
int rev[MAXN];
ll inv[MAXN], F[MAXN], G[MAXN];
void initinv(int n)
{
    inv[1] = 1;
    for (int i = 2; i <= n; i++) inv[i] = (p - p / i) * inv[p % i] % p;
}
void Dert(int n, ll *F, ll *G)
{
    for (int i = 1; i < n; i++) G[i - 1] = F[i] * i % p;
}
void Int(int n, ll *F, ll *G)
{
    for (int i = 0; i < n; i++) G[i + 1] = F[i] * inv[i + 1] % p;
}
void NTT(ll *A, int n, int op)
{
    for (int i = 0; i < n; i++)
        if (i < rev[i]) swap(A[i], A[rev[i]]);
    for (int i = 2; i <= n; i <<= 1)
    {
        ll g1 = qpow(op == 1 ? g : gi, (p - 1) / i);
        for (int j = 0; j < n; j += i)
        {
            ll gk = 1;
            for (int k = j; k < j + i / 2; k++)
            {
                ll x = A[k], y = A[k + i / 2] * gk % p;
                A[k] = (x + y) % p;
                A[k + i / 2] = (x - y + p) % p;
                gk = gk * g1 % p;
            }
        }
    }
    if (op == 1) return;
    ll ni = getinv(n);
    for (int i = 0; i < n; i++) A[i] = A[i] * ni % p;
}
void Inv(int n, ll *F, ll *G)
{
    static ll A[MAXN], B[MAXN];
    G[0] = getinv(F[0]);
    int len, lim;
    for (len = 1; len < (n << 1); len <<= 1)
    {
        lim = len << 1;
        copy(F, F + len, A), copy(G, G + len, B);
        for (int i = 0; i < lim; i++)
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * len);
        NTT(A, lim, 1), NTT(B, lim, 1);
        for (int i = 0; i < lim; i++)
            G[i] = ((2 - A[i] * B[i] % p) * B[i] % p + p) % p;
        NTT(G, lim, -1);
        fill(G + len, G + lim, 0);
    }
    fill(A, A + len, 0), fill(B, B + len, 0), fill(G + n, G + len, 0);
}
void Ln(int n, ll *F, ll *G)
{
    static ll A[MAXN], B[MAXN];
    Inv(n, F, A), Dert(n, F, B);
    int lim;
    for (lim = 1; lim < (n << 1); lim <<= 1);
    for (int i = 0; i < lim; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (lim >> 1));
    NTT(A, lim, 1), NTT(B, lim, 1);
    for (int i = 0; i < lim; i++) A[i] = A[i] * B[i] % p;
    NTT(A, lim, -1), fill(A + n, A + lim, 0), Int(n - 1, A, G);
}
void Exp(int n, ll *F, ll *G)
{
    static ll A[MAXN], B[MAXN];
    int lim, len;
    G[0] = 1;
    for (len = 1; len < (n << 1); len <<= 1)
    {
        lim = len << 1;
        copy(F, F + len, A), Ln(len, G, B);
        for (int i = 0; i < lim; i++)
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (lim >> 1));
        NTT(A, lim, 1), NTT(B, lim, 1), NTT(G, lim, 1);
        for (int i = 0; i < lim; i++)
            G[i] = (1 - B[i] + A[i] + p) % p * G[i] % p;
        NTT(G, lim, -1), fill(A, A + lim, 0), fill(B, B + lim, 0);
    }
    fill(G + n, G + len, 0);
}
ll cnt[MAXN], n, m;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    initinv(4e5);
    cin >> n >> m;
    for (int v, i = 1; i <= n; i++) cin >> v, cnt[v]++;
    for (ll i = 1; i <= m; i++)
        if (cnt[i])
            for (ll j = 1; j <= m / i; j++)
                F[i * j] = (F[i * j] + cnt[i] * (p - inv[j])) % p;
    Exp(m + 1, F, G), memset(F, 0, sizeof(F)), Inv(m + 1, G, F);
    for (int i = 1; i <= m; i++) cout << F[i] << endl;
    return 0;
}