更新了两道例题辣

多项式板子见另一篇博文。

Orzlsj

定义

• 普通生成函数 OGF 对于数列 $\{a_i\}$ ，OGF 是：

  $$A(x) = \sum_{i\ge 0} a_ix^i$$

• 指数生成函数 EGF EGF 是：

  $$A(x) = \sum_{i\ge 0} a_i\frac{x^i}{i!}$$

这两个有什么用？ OGF 一般解决无标号有序的问题，EGF 一般解决有标号有序的问题。

OGF

两个 OGF 的乘积 $A(x)\times B(x)$ 可以理解为 从 $A$ 中选择一个元素，再从 $B$ 中选择一个元素，然后拼接起来。

举个栗子，设 $a_n$ 表示 $n$ 个完全相同的求放入 $1\sim 5$ 编号的篮子的方案数量，其中 $1,2$ 篮子内球必须是偶数，剩下的三个篮子内球数必须介于 $3\sim 5$ ，求 $a_n$ 的 OGF 。

就是：

$$(x^0+x^2+x^4+\cdots )^2(x^3+x^4+x^5)^2$$

这个多项式的第 $n$ 项就是最终放了 $n$ 个球的方案数量。

EGF

指数生成函数的乘积 $C(x) = A(x) \times B(x)$ 可以理解为当前 $A,B$ 的元素已经分别分配好了编号，我们需要讲这些元素组合起来并重新分配编号，并且不能改变原来的大小关系。（然后直接从课件扒公式）

$$\begin{aligned} \hat{C}(x) &=\hat{A}(x) \times \hat{B}(x) \\ \frac{C_{n}}{n !} &=\sum_{i+j=n} \frac{A_{i}}{i !} \times \frac{B_{j}}{j !} \\ C_{n} &=\sum_{i+j=n} A_{i} \times B_{j} \times\left(\begin{array}{c} i+j \\ i \end{array}\right) \end{aligned}$$

个人感觉这个定义可能不是很直观。看一个栗子，设 $a_n$ 为 $n$ 个不同的球放入 $k$ 个不同盒子的方案数，盒子可以空，求 $a_n$ 的 EGF。

考虑对于每个盒子，如果我们决定它要放进去 $x$ 个球，很明显这 $x$ 个球是不存在顺序的，也就是说它们“已经被分配好了编号”。

钦定一个放入的顺序后，这个东西就是

$$(\sum_{0\le i\le n}\frac{x^i}{i!})^k$$

如果你和 yijan 一样到这里都还是有点晕，建议看看后面的 Q2。

一些展开式

$$(a+b)^n = \sum_{i=0}^n {n \choose i} a^ib^{n-i}\\ \frac{1}{1-x} = 1 + x + x^2 + \cdots \\ -\ln(1-x) = x + \frac{x^2} 2 + \frac{x^3}{3}+\cdots\\ \exp(x) = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots$$

很重要。

注意，展开式的 $x$ 既可以是 $x$ 又可以是一个多项式，这在后面会反复用到。

多项式求逆

众所周知，一个多项式求逆后是一个无穷次项的玩意。但是我们一般只需要它的前 $n$ 项。

我们需要算出：

$$A\times B \equiv 1 \pmod {x^n}$$

这东西怎么做？背板 我们可以考虑倍增来求解。

首先如果 $A$ 仅有一项，那么 $B[0]$ 就是 $A[0]$ 的逆元。

否则，假设我们已经有了

$$A\times B' \equiv 1\pmod {x^{\lceil\frac n 2\rceil}}\\$$

同时我们必然有真正的 $B$ 在模 $x^{\lfloor\frac n 2 \rfloor }$ 的时候也是 $1$ ，也就是说有

$$A\times B \equiv 1\pmod {x^{\lceil\frac n 2\rceil}}$$

那么考虑两个式子相减

$$A \times ( B - B' ) \equiv 0 \pmod {x^{\lceil\frac n 2\rceil}}$$

由于 $A$ 显然不同余于 $0$ ，所以有

$$B - B' \equiv 0 \pmod {x^{\lceil\frac n 2\rceil}}$$

所以我们可以平方一下，把模的位置翻倍，并且由于是向上取整，我们知道前 $n$ 项都会是 $0$。

$$(B-B')^2 \equiv 0 \pmod {x^{n}}\\ B^2 - 2BB' + B'^2 \equiv 0 \pmod {x^{n}}\\$$

然后我们可以给式子的一遍乘上一个 $A$ ，仍然前 $n$ 项是 $0$ ：

$$A(B^2 - 2BB' + B'^2) \equiv 0 \pmod {x^{n}}\\$$

由于 $AB$ 显然是 $1$ ，所以我们拆开有

$$B - 2B' + AB'^2 \equiv 0 \pmod {x^{n}}\\$$

所以移项后有

$$B \equiv 2B' - AB'^2 \pmod {x^n}\\ B \equiv B'(2 - AB') \pmod {x^{n}}\\$$

这个东西复杂度用主定理分析出来是 $O(n\log n)$ 而不是 $O(n\log ^2n)$ 哦。

多项式 ln

我们考虑

$$B = \ln A$$

两边导一下：

$$B' = \frac{1}{A} A'$$

所以我们可以对 $A$ 求逆乘上 $A’$ 然后再做个积分就完事了。

泰勒展开

如何将一个多项式 $F(x)$ 展开成 无穷级数 的形式呢？

我们知道，对于一个 $F(x)$ 有唯一的导函数 $F’(x)$ 。

但是我们不能通过导数来推会原函数，因为很多函数的导函数会对应到同一个 $F’(x)$ ，具体来说，这类函数是 $F(x) + C$。

但是我们如果有一个初始点，就可以求得 $C$ ，并通过导函数推回原函数了。

我们可以选择一个点 $x_0$ 来获取 $F(x)$ 的初始信息，我们称 $x_0$ 为展开点。先来考虑 $x_0 = 0$ 的情况

$$\begin{aligned} F(x) &=\int_{0}^{x} F^{\prime}(x) \mathrm{d} x+F(0) \\ &=\int_{0}^{x}\left[\int_{0}^{x} F^{\prime \prime}(x) \mathrm{d} x+F^{\prime}(0)\right] \mathrm{d} x+F(0) \\ &=\int_{0}^{x} \int_{0}^{x} F^{\prime \prime}(x) \mathrm{d} x \mathrm{d} x+\int_{0}^{x} F^{\prime}(0) \mathrm{d} x+F(0)\\ &= \cdots \end{aligned}\\$$

我们可以一直这样套娃下去，得到

$$\begin{aligned} F(x) &= F(0) + \int_0^x F'(0)\mathrm dx + \int_0^x\int_{0}^xF''(0)\mathrm{d}x\mathrm{d}x+\cdots\\ &= F(0) + \frac{F'(0)x}{1} + \frac{F''(0)x^2}{2 \times 1} + \cdots\\ &= \sum_{i \ge 0} \frac{F^{(i)}(0)x^i}{i!} \end{aligned}$$

现在我们考虑更加一般的情况。假如我们的展开点是 $a$ 呢？

$$\begin{aligned} F(x) &= \int_{a}^x F'(x)\mathrm dx + F(a)\\ &= F(a) + \int_{a}^x F'(a)\mathrm dx + \int_a^x\int_a^x F''(a)\mathrm dx\mathrm dx + \cdots \end{aligned}$$

令 $u = x-a$ 来换元，让下标作为 $0$

$$\begin{aligned} F(x) &= F(a) + \int_{0}^u F'(a)\mathrm du + \int_0^u\int_0^u F''(a)\mathrm du\mathrm du\\ &= \sum_{i \ge 0} \frac{F^{(i)}(a) u^i}{i!}\\ &= \sum_{i \ge 0} \frac{F^{(i)}(a)(x-a)^i}{i!} \end{aligned}$$

一个很一般的问题

已知 $G(F(x)) \equiv 0 \pmod {x^n}$ ，给出 $G$ 求 $F$ 。

设 $F_t(x)$ 表示 $t$ 次迭代后的 $F(x)$ ，那么满足

$$G(F_t(x)) \equiv 0 \pmod{x^{2^t}}$$

然后考虑将 $G(F_{t+1}(x))$ 从 $F_t(x)$ 处展开，那么

$$\begin{aligned} G\left[F_{t+1}(x)\right] &=\sum_{i \geq 0} \frac{G^{(i)}\left[F_{t}(x)\right]}{i !}\left[F_{t+1}(x)-F_{t}(x)\right]^{i} \\ \end{aligned}$$

我们考虑当 $i \ge 2$ 的时候，由于 $F_{t+1}(x),F_{t}(x)$ 在模 $x^{2^t}$ 的时候都已经爆零了，那么 $[F_{t+1}(x)-F_t(x)]^i$ 在模 $x^{2^{t+1}}$ 的时候也一定爆零了，所以我们只需要提取出 $i < 2$ 的时候的式子就一定同余 $0$。

$$\begin{aligned}&=G\left[F_{t}(x)\right]+G^{\prime}\left[F_{t}(x)\right] \times\left[F_{t+1}(x)-F_{t}(x)\right]+\sum_{i \geq 2} \cdots \\0 & \equiv G\left[F_{t}(x)\right]+G'\left[F_{t}(x)\right] \times\left[F_{t+1}(x)-F_{t}(x)\right] \quad\left(\bmod x^{2 ^{t+1}}\right) \\F_{t+1}(x) & \equiv F_{t}(x)-\frac{G\left[F_{t}(x)\right]}{G^{\prime}\left[F_{t}(x)\right]} \quad\left(\bmod x^{2 ^{t+1}}\right)\end{aligned}$$

这里的 $G’(F(x))$ 应当先算出 $G’(x)$ 再带入 $F(x)$ ，而不是复合的求导。

如果你很懵的话，可以看下下面这个例子。

多项式 exp

已知 $B(x) \equiv \exp A(x) \pmod{x^n}$ ，给定 $A(x)$ 求出 $B(x)$。

首先考虑构造 $G(x)$ ，满足 $G(B(x)) = 0$ ，那么

$$G(B(x)) = \ln B(x) - A(x)$$

我们知道

$$G'(B(x)) = \frac{1}{B(x)}$$

那么带入前面那个公式

$$\begin{aligned} B_{t+1}(x) &= B_t(x) - \frac{G(B_t(x))}{G'(B_t(x))} \pmod{x^{2^{t+1}}}\\ &= B_t(x) - \frac{\ln B_t(x)-A(x)}{\frac{1}{B_t(x)}}\pmod{x^{2^{t+1}}}\\ &= B_t(x) - B_t(x)( \ln B_t(x) - A(x) )\pmod{x^{2^{t+1}}}\\ &= B_t(x)[1 - \ln B_t(x) + A(x)] \pmod{x^{2^{t+1}}} \end{aligned}$$

实现上，我们可以先递归下去算出 $B’(x) \equiv A(x) \pmod {\lceil\frac{n}{2}\rceil}$ ，然后通过上面那个式子把它变成 $B(x) \pmod {x^n}$ 。

复杂度也可以分析得 $O(n\log n)$ 但是常数很大。（虽然据说论文哥可以让它跑得比我写的 NTT 还快）

经典问题

Q1

有若干不同颜色的骨牌，大小为 $1\times i$ 的有 $a_i$ 种，每种骨牌数量无限，问恰好填满 $1\times n$ 的格子的方法。颜色相同的骨牌没有区别。

假设我们用 $i$ 张骨牌来填，那么当前所填满的格子的个数的生成函数是

$$A(x)^i$$

所以答案就是

$$\sum_{i\ge 0} A(x)^i = \frac 1 {1-A(x)}$$

Q2

给定集合 $S$ 与正整数 $n$ ，求 $n$ 阶置换 $p$ 的数量，满足 $p$ 分解后的每个轮换大小都在 $S$ 之内。

我们考虑一个置换其实是由很多轮换一起构成的。我们假设原置换分解出了一个长度为 $k$ 的轮换，显然这个轮换的只和它的形态有关，与编号无关，比如 1,2,3,4 和 2,3,4,1 是同一个轮换。所以一个轮换内的形态个数实际上是 $(k-1)!$ ，也就是圆排列的数量。

然后我们知道，对于轮换组成置换而言，我们应当使用 EGF 而不是 OGF。因为我们构造出的“置换”显然是有标号的，使用 EGF 可以提前给一个轮换内部钦定标号方案。如果我们构造一个轮换，EGF 为：

$$\hat F(x) = \sum_{i \in S} (i-1)!\frac{x^i}{i!}$$

然后我们考虑轮换组成置换这个过程，显然它是无序的。因为我们加入 (3,4)(1,2) 和 (1,2)(3,4) 本质上是一样的。我们假设枚举置换由多少轮换组成，那么：

$$\hat G(x) = \sum_{i\ge 0} \frac{\hat F(x)}{i!}\\\hat G(x) = \exp(\hat F(x))$$

Q3

你有很多物品，体积为 $i$ 的有 $a_i$ 种，每种物品数量无限。求选取物品恰好装满容量为 $n$ 的背包方案数。

如果按照原来的思路直接上 OGF 显然会暴毙。因为这道题装物品这个动作已经变成无序的了。

于是我们考虑拿了体积为 $i$ 的物品多少个这个问题，惊奇的发现这个问题就是可以强行钦定顺序的了！我们可以先尝试拿了多少个体积为 $1$ 的，再尝试拿了多少个体积为 $2$ 的 …

由于体积为 $i$ 的有 $a_i$ 种，于是如果我们只拿体积为 $i$ 的能组成每个体积的方案数量为

$$(x^0+x^i+x^{2i} + \cdots)^{a_i}$$

于是答案的 OGF 就是

$$\prod_{i=1}^n (\sum_{k\ge 0} x^{ki})^{a_i}$$

里面是一个展开式

$$\prod_{i=1}^n(\frac 1 {1-x^i})^{a_i}$$

往往这种不太好处理的求积可以先 $\ln$ 再 $\exp$

$$\begin{aligned} &= \exp\left(\sum_{i=1}^n a_i\ln((1-x^i)^{-1})\right)\\ &= \exp\left(\sum_{i=1}^n a_i(-\ln(1-x^i))\right) \end{aligned}$$

这后面又是一个展开式！

$$= \exp\left(\sum_{i=1}^n a_i{\sum_{j\ge 1}\frac{x^{ij}}{j}}\right)$$

我们尝试交换循环顺序

$$=\exp\left(\sum_{j\ge 1} \frac{\sum_{i=1}^n a_ix^{ij}}{j} \right)$$

我们设 $\{a_ix^i\}$ 的 OGF 是 $G(x)$ 那么

$$=\exp\left(\sum_{j\ge 1} \frac{G(x^j)}{j} \right)$$

然后我们可以枚举 $j$ 算出 $\frac{G(x^j)}{j}$ 算出来求和再 $\exp$ 就做完了。后面求和部分相当于是 $n + \frac n 2 + \frac n 3 + \cdots$ ，也就是 $O(n\ln n)$ ，再做一次 $\exp$ 总复杂度 $O(n\log n)$ 。

原题连接

我不会的题

某个 JZOI 的题

首先，最后一次染色的颜色必定会在序列中出现。并且如果删除（这里是指删除这些格子）了最后一次出现的颜色，那么倒数第二次加入的颜色要么不出现，要么连续。我们可以递归做这个过程，从任何一种结束状态可以推出唯一一个 删除 - 拼接序列。

由于操作具有顺序，删除拼接序列对应着唯一一个“插入”序列。也就是说如果我们正着做这个 删除 - 拼接 操作，开始有一个空的序列，每次操作选择一个位置，从这里切开并且插入一个长度固定的连续段，满足最后序列的长度为 $n$ 。而这里插入的长度必然是你删除时删除的这段的长度，插入的位置必然就是你删除后拼接的位置。

明显，一种插入操作对应着唯一的一种结束状态。所以我们知道了我们本质上要统计的是插入操作的方案数量，必须满足

• 插入结束时，整个序列长度为 $n$
• 由于最后第 $m$ 种颜色必然出现在序列里面，也就是说最后一次插入的长度不为 $0$ 。

我们设 $dp[i][j]$ 表示前 $i$ 个颜色，当前序列长度为 $j$ 的方案个数，我们考虑要么沿用 $dp[i-1][j]$ 要么我们可以从 $dp[i-1][k]$ 转移过来，也就是在 $k+1$ 个位置中选择一个位置插入长度 $j-k$。

$$dp[i][j] = dp[i-1][j] + \sum_{k=0}^{j-1} dp[i-1][k]\times (k+1)$$

这个东西该怎么优化？我们可以想办法把 $\sum$ 前的部分给拿掉。更改一下 $dp$ 的定义，现在 $dp[i][j]$ 表示前 $i$ 个颜色，当前序列长度为 $j$ ，并且每个颜色必须出现至少一次。最后的答案就是这个 $dp$ 算出的答案来乘个 $m-1 \choose i-1$ ，因为最后一种颜色必然出现。

$$dp[i][j]=\sum_{k=0}^{j-1} dp[i-1][k] \times(k+1)$$

考虑稍微变形一下，让它变成一个递推的形式

$$\begin{aligned} dp[i][j] &= \sum_{k=1}^{j-2} dp[i-1][k] \times (k + 1) + dp[i-1][j-1]\times j\\ &= dp[i][j-1] + dp[i-1][j-1] \times j \end{aligned}$$

然后就要开始神仙操作了：

我们可以把 $dp$ 看作是在一张 $n\times m$ 的网格上行走，从 $(1,1)$ 出发，每次可以向下走一格，方案数为 $1$ ，向右下走一格，方案数为 $j+1$（当前行数 + 1）。

盗用一下 LSJ 爷爷画的图：

我们现在需要求出的，就是每个终点的权值。

我们考虑每次行走要么当前列不变，要么 + 1，我们用 $x$ 的指数来代替列数，于是 $F_i = dp[i][n]$ 的 OGF 为：

$$F(x) = x \prod_{i=1}^{n-1} (1+(i+1)x)$$

其中乘上 $x$ 是由于是从 $(1,1)$ 开始行走的，默认有 $1$ 列。

然后这个式子还是不太可做。

我们考虑，总步数必然是 $n$ ，所以也可以把向下一步看成 $x$ ，那么最终多项式中 $x^i$ 的系数就是原来多项式 $x^{n-i}$ 的系数。

$$F'(x) = \prod_{i=1}^{n-1} (x+i+1)$$

这东西可做？答案是它确实可做。我们可以倍增求这个式子。

令 $G_t(x) = \prod_{i=1}^{2^t} (x+i+1)$，我们现在希望能算出所有的 $G$

$$G_{t+1}(x) = G_t(x) \times G_t(x+2^t)$$

我们令 $a_i = [x^i]G_t(x),b=2^t$ 那么

$$G_t(x+b) = \sum_{i\ge 0} a_i(x+b)^i$$

我们运用二项式定理展开一下，再交换循环次序化简

$$\begin{aligned} G_{t}(x+b) &=\sum_{i \geq 0} a_{i} \times(x+b)^{i} \\ &=\sum_{i \geq 0} a_{i} \sum_{j=0}^{i}\left(\begin{array}{c} i \\ j \end{array}\right) x^{j} b^{i-j} \\ &=\sum_{j \geq 0} x^{j} \sum_{i \geq j} a_{i} b^{i-j} \frac{i !}{j !(i-j) !} \\ &=\sum_{j \geq 0} \frac{x^{j}}{j !} \sum_{i \geq j}\left(a_{i} i !\right) \times \frac{b^{i-j}}{(i-j) !} \end{aligned}$$

单独看下后面那个东西

$$\begin{aligned} T(j) &= \sum_{i\ge j} (i!a_i) \times \frac{b^{i-j}}{(i-j)!}\\ &=\sum_{i-k=j} (i!a_i) \times \frac{b^k}{k!} \end{aligned}$$

明显它是两个多项式的差卷积。

所以

$$G_t(x+b) = \sum_{j\ge 0} T(j)\frac{x^j}{j!}$$

于是我们可以通过 $G_t$ 在 $O(n\log n)$ 的时间内推出 $G_t(x + b)$ 从而可以快速得知 $G_{t+1}(x)$ 。

然后就可以类似 ksm 做完了。

一份很丑的代码

int n , m;
int J[MAXN] , iJ[MAXN];

inline int Pow( int x , int a ) {
    int ans = 1 , cur = x % P;
    while( a ) {
        if( a & 1 ) ans = 1ll * ans * cur % P;
        cur = 1ll * cur * cur % P , a >>= 1;
    }
    return ans;
}

int Wn[2][MAXN] , rev[MAXN];
inline void getwn( int len ) {
    for( int mid = 1 ; mid < len ; mid <<= 1 ) {
        int w0 = Pow( 3 , ( P - 1 ) / ( mid << 1 ) ) , w1 = Pow( 3 , P - 1 - ( P - 1 ) / ( mid << 1 ) );
        Wn[0][mid] = Wn[1][mid] = 1;
        for( int i = 1 ; i < mid ; ++ i )
            Wn[0][mid + i] = 1ll * Wn[0][mid + i - 1] * w0 % P,
                    Wn[1][mid + i] = 1ll * Wn[1][mid + i - 1] * w1 % P;
    }
}
inline void getr( int len ) {
    int t = __builtin_ctz( len ) - 1;
    for( int i = 1 ; i < len ; ++ i ) rev[i] = ( rev[i >> 1] >> 1 ) | ( ( i & 1 ) << t );
}
int cn;
inline void NTT( int* A , int len , int typ ) {
//    cout << len << ' ' << ++ cn << endl;
    rep( i , 0 , len - 1 ) if( i < rev[i] ) swap( A[i] , A[rev[i]] );
    for( int mid = 1 ; mid < len ; mid <<= 1 )
        for( int i = 0 ; i < len ; i += ( mid << 1 ) )
            for( int k = 0 ; k < mid ; ++ k ) {
                int t1 = A[i + k] , t2 = 1ll * A[i + k + mid] * Wn[typ][mid + k] % P;
                A[i + k] = (t1 + t2) % P , A[i + k + mid] = (t1 + P - t2) % P;
            }
    if( typ == 1 ) for( int inv = Pow( len , P - 2 ) , i = 0 ; i < len ; ++ i ) A[i] = 1ll * A[i] * inv % P;
}

int G[MAXN] , ans[MAXN] , cur , ret[MAXN];


int tG[MAXN] , tb[MAXN];
inline void Make_Your_Dream_COMETRUE( int n , int b , int ok ) { // ok ? G_t -> G_{t+1} : G_t -> G_t(x+b) , n : 2^t
    rep( i , 0 , n ) tG[i] = 1ll * J[i] * G[i] % P , tb[n - i] = 1ll * Pow( b , i ) * iJ[i] % P;
    int len = 1 , l = 0;
    while( len <= n + n ) len <<= 1;
    rep( i , n + 1 , len ) tG[i] = tb[i] = 0;
    getr( len ) , getwn( len );
    NTT( tG , len , 0 ) , NTT( tb , len , 0 );
    rep( i , 0 , len - 1 ) ret[i] = 1ll * tG[i] * tb[i] % P;
    NTT( ret , len , 1 );
    rep( i , 0 , n ) ret[i] = 1ll * ret[i + n] * iJ[i] % P;
    rep( i , n + 1 , len - 1 ) ret[i] = 0;
    if( !ok ) return;
    NTT( ret , len , 0 ) , NTT( G , len , 0 );
    rep( i , 0 , len - 1 ) G[i] = 1ll * ret[i] * G[i] % P;
    NTT( G , len , 1 );
}

void Just_DOIT( int x ) {
    G[0] = 2 , G[1] = 1 , cur = 1;
    ans[0] = 1;
    int re = 0 , len , l;
    while( x ) {
        if( x & 1 ) {
            Make_Your_Dream_COMETRUE( cur , re , 0 );
            len = 1;
            while( len <= cur + cur ) len <<= 1;
            NTT( ans , len , 0 ) , NTT( ret , len , 0 );
            rep( i , 0 , len - 1 ) ans[i] = 1ll * ans[i] * ret[i] % P;
            NTT( ans , len , 1 );
            re += cur;
        }
        x >>= 1;
        if( x ) Make_Your_Dream_COMETRUE( cur , cur , 1 ); cur <<= 1;
    }
}

int C( int a , int b ) {
    if( a < b ) return 0;
    return 1ll * J[a] * iJ[b] % P * iJ[a - b] % P;
}

void solve() {
    J[0] = iJ[0] = 1;
    rep( i , 1 , MAXN - 1 ) J[i] = 1ll * i * J[i - 1] % P , iJ[i] = Pow( J[i] , P - 2 );
    cin >> n >> m;
//    puts("w");
    Just_DOIT( n - 1 );
//    puts("w");
    int re = 0;
    rep( i , 1 , n ) ( re += 1ll * ans[n - i] * C( m - 1 , i - 1 ) % P ) %= P;
    cout << re << endl;
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

一个不知道从哪里来的神仙题

我们考虑一开始的概率的 OGF $F(x)$ ，经过一次操作之后变成了 $F_1(x)$ 。那么：

$$[x^i]F_1(x) = \sum_{j=i}^n \frac{[x^j]F(x)}{j+1}\\\begin{aligned}F_1(x) &= \sum_{i=0}^n x^i\sum_{j=i}^n \frac{[x^j]F(x)}{j+1}\\&= \sum_{j=0}^n \frac{[x^j]F(x)}{j+1} \sum_{i=0}^j x^i\\&=\frac 1 {x - 1} \sum_{j=0}^n \frac{[x^j]F(x)}{j+1} (x^{j+1} - 1)\end{aligned}$$

然后就要开始变魔法了，我们考虑

$$\frac{x^{j+1}-1}{j+1} = \int_{1}^x t^j \mathrm dt$$

把这个 int 带进去

$$\begin{aligned}F_1(x) = \frac{1}{x - 1}\sum_{j=0}^n [x^j]F(x) \int_{1}^x t^j \mathrm dt\end{aligned}$$

我们知道 $[x^j]F(x)$ 其实是一个常数，把它放进积分里面

$$F_1(x) = \frac{1}{x - 1}\sum_{j=0}^n \int_{1}^x [x^j]F(x) t^j \mathrm dt$$

明显，求和也是可以放在积分里面的，分别积分后求和和求和后再做积分没有区别

$$F_1(x) = \frac{1}{x - 1} \int_{1}^x\sum_{j=0}^n [x^j]F(x) t^j \mathrm dt$$

有没有看出些什么？后面那个式子就是 $F(t)$ ！

$$F_1(x) = \frac{1}{x - 1} \int_{1}^x F(t) \mathrm dt$$

发现这个式子很难搞， $\frac 1 {x-1}$ 不太好用，积分也是从 $1$ 开始的，这意味着我们得算出 $F(1)$，有没有办法解决这两个问题？

我们设 $G(x) = F(x+1),G_1(x) = F_1(x+1)$ ，也就是把 $F$ 左移 $1$ ，那么式子会变得很好看：

$$G_1(x) = \frac 1 x \int_0^x G(t)\mathrm dt$$

化简它！我们设 $g_i = [x^i]G$

$$\begin{aligned}G_1(x) &= \frac 1 x \int_0^x G(t)\mathrm dt\\&= \frac 1 x \sum_{i=0}^n \int_{0}^x g_it^i \mathrm dt\\&= \frac 1 x \sum_{i=0}^n [\frac{g_i}{i+1}t^{i+1}]_0^x\\&= \frac 1 x \sum_{i=0}^n \frac{g_i}{i+1} x^{i+1}\\&= \sum_{i=0}^n \frac{g_i}{i+1} x^i\end{aligned}$$

也就是说从 $G(x)$ 到 $G_1(x)$ 只需要每一项除个 $i+1$ ！

然后现在唯一的问题就是如何算 $G(x) = F(x + 1) , F_m(x) = G_m(x-1)$ 了，直接二项式定理展开推一下就好了,如果不会可以参考 HDU6061 RXD and functions 这题。

int n , A[MAXN];
ll m;
int Pow( int x , int a ) {
    int ret = 1;
    while( a ) {
        if( a & 1 ) ret = 1ll * ret * x % P;
        x = 1ll * x * x % P , a >>= 1;
    }
    return ret;
}

int Wn[2][MAXN] , rev[MAXN];
void getwn( int len ) {
    for( int mid = 1 ; mid < len ; mid <<= 1 ) {
        int w0 = Pow( 3 , ( P - 1 ) / ( mid << 1 ) ) , w1 = Pow( 3 , P - 1 - ( P - 1 ) / ( mid << 1 ) );
        Wn[0][mid] = Wn[1][mid] = 1;
        for( int i = 1 ; i < mid ; ++ i )
            Wn[0][mid + i] = 1ll * Wn[0][mid + i - 1] * w0 % P,
                    Wn[1][mid + i] = 1ll * Wn[1][mid + i - 1] * w1 % P;
    }
}
void getr( int len ) {
    int t = __builtin_ctz( len ) - 1;
    for( int i = 1 ; i < len ; ++ i ) rev[i] = ( rev[i >> 1] >> 1 ) | ( ( i & 1 ) << t );
}
void NTT( int* A , int len , int typ ) {
    rep( i , 0 , len - 1 ) if( i < rev[i] ) swap( A[i] , A[rev[i]] );
    for( int mid = 1 ; mid < len ; mid <<= 1 )
        for( int i = 0 ; i < len ; i += ( mid << 1 ) )
            for( int k = 0 ; k < mid ; ++ k ) {
                int t1 = A[i + k] , t2 = 1ll * A[i + k + mid] * Wn[typ][mid + k] % P;
                A[i + k] = (t1 + t2) % P , A[i + k + mid] = (t1 + P - t2) % P;
            }
    if( typ == 1 ) for( int inv = Pow( len , P - 2 ) , i = 0 ; i < len ; ++ i ) A[i] = 1ll * A[i] * inv % P;
}

int J[MAXN] , iJ[MAXN];

int tt[MAXN];
void move( int A[] , int d ) { // A -> A (x + d)
    rep( i , 0 , n ) A[i] = 1ll * J[i] * A[i] % P , tt[n - i] = ( ( d == 1 ? 1ll : ( ( i & 1 ) ? -1ll : 1ll ) ) * iJ[i] + P ) % P;
    int len = 1;
    while( len <= n + n ) len <<= 1;
    rep( i , n + 1 , len ) tt[i] = 0;
    getwn( len ) , getr( len );
    NTT( A , len , 0 ) , NTT( tt , len , 0 );
    rep( i , 0 , len - 1 ) A[i] = 1ll * A[i] * tt[i] % P;
    NTT( A , len , 1 );
    rep( i , 0 , n ) A[i] = 1ll * A[i + n] * iJ[i] % P;
    rep( i , n + 1 , len - 1 ) A[i] = 0;
}
void solve() {
//    cout << 5ll * Pow( 18 , P - 2 ) % P << endl;
    cin >> n >> m;
    m %= P - 1;
    J[0] = iJ[0] = 1;
    rep( i , 1 , n ) J[i] = 1ll * J[i - 1] * i % P , iJ[i] = Pow( J[i] , P - 2 );
    rep( i , 0 , n ) scanf("%d",A + i);
    move( A , 1 );
    rep( i , 0 , n ) A[i] = 1ll * A[i] * Pow( i + 1 , 1ll * ( P - 2 ) * (m) % ( P - 1 ) ) % P;
    move( A , -1 );
    rep( i , 0 , n ) printf("%d ",A[i]);
}

signed main() {
//    freopen("in1.in","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}