Description：

初始时有一个正整数 $n$ ，初始为 $i$ 的概率是 $p_i$ 。每一轮从 $[0,n]$ 内随机选取一个正整数 $p$ ，把 $n$ 替换成 $p$ 。

给定 $M$ , 对每个 $i\in [1,n]$ 求 $M$ 轮之后这个数为 $i$ 的概率。

$i\leqslant n\leqslant 10^5, 1\leqslant M\leqslant 10^{18}$

Solution：

设当前取到 $i$ 的概率为 $f_i$ ，操作之后取到 $i$ 的概率为 $f'_i$ ，那么有： $$ f_i'=\sum_{j=i}^n\frac{f_j}{j+1} $$ 设 $f_i$ 的生成函数为 $F(x)$ ，那么有： $$ \begin{align} F(x)&=\sum_{i=0}^nf_ix^i\\ F'(x)&=\sum_{i=0}^nf'_ix^i\\ &=\sum_{i=0}^n\sum_{j=i}^n\frac{f_j}{j+1}x^i\\ &=\sum_{j=0}^n\frac{f_j}{j+1}\sum_{i=0}^jx^i\\ &=\sum_{j=0}^n\frac{f_j}{j+1}\frac{x^{j+1}-1}{x-1}\\ &=\frac1{x-1}\sum_{j=0}^nf_j\frac{x^{j+1}-1}{j+1}\\ &=\frac1{x-1}\sum_{j=0}^nf_j\int^x_1t^j\mathrm{d}t\\ &=\frac{\int^x_1F(t)\mathrm dt}{x-1} \end{align} $$ 这个东西不是很好处理，因为积分下限和分母都不太好做，这时有一个技巧就是设 $G(x)=F(x+1)$ ，那么： $$ G'(x)=F'(x+1)=\frac{\int^{x+1}_1F(t)\mathrm dt}{x+1-1}=\frac{\int_0^xF(t+1)\mathrm dt}x=\frac{\int^x_0G(t)\mathrm dt}x $$ 因此有： $g'_i=[x^{i+1}]\int_0^xG(t)\mathrm dt=\frac{g_i}{i+1}$ ，因此进行 $m$ 次操作就是 $g_i'=\frac{g_i}{(i+1)^m}$ 。

最后我们只要解决一个问题：如何让 $f$ 和 $g$ 互相转换。 $$ G(x)=F(x+1)=\sum_{i=0}^nf_i(x+1)^i=\sum_{i=0}^nf_i\sum_{k=0}^i\binom ikx^k=\sum_{k=0}^n\Big(\sum_{i=k}^n\binom ikf_i\Big )x^k $$ 也就是说： $$ g_k=\sum_{i=k}^n\binom ik f_i=\frac 1{k!}\sum_{i=k}^ni!f_i\frac1{(i-k)!} $$ 根据二项式反演： $$ f_k=\sum_{i=k}^n(-1)^{i-k}\binom ikg_i=\frac1{k!}\sum_{i=k}^ni!g_i\frac{(-1)^{i-k}}{(i-k)!} $$ 于是就可做了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

int n;

ll m;

#define MAXN 400010

int F[MAXN],G[MAXN];

#define N 100000

int fac[MAXN],inv[MAXN];

#define P 998244353

int power(int a,int b)

{

	int res = 1;

	for(;b > 0;b = b >> 1,a = 1ll * a * a % P)if(b & 1)res = 1ll * res * a % P;

	return res;

}

int inver(int a){return power(a,P - 2);}

int A[MAXN],B[MAXN];

int rev[MAXN];

int ww[MAXN << 1],*g = ww + MAXN;

int init(int n)

{

	int l = 0,len = 1;

	for(;len <= n;len = len << 1)++l;

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = 1ll * g[i - 1] * g[1] % P;

	return len;

}

void NTT(int f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		int wn = g[type * l / i];

		for(int j = 0;j < l;j += i)

		{

			int w = 1;

			for(int k = j;k < j + i / 2;++k)

			{

				int u = f[k],t = 1ll * w * f[k + i / 2] % P;

				f[k] = (u + t) % P;

				f[k + i / 2] = (u - t + P) % P;

				w = 1ll * w * wn % P;

			}

		}

	}

	if(type == -1)

	{

		int ni = power(l,P - 2);

		for(int i = 0;i < l;++i)f[i] = 1ll * f[i] * ni % P;

	}

	return;

}

int main()

{

	scanf("%d%I64d",&n,&m);

	m %= (P - 1);

	for(int i = 0;i <= n;++i)scanf("%d",&F[i]);

	fac[0] = 1;for(int i = 1;i <= n;++i)fac[i] = 1ll * fac[i - 1] * i % P;

	inv[n] = inver(fac[n]);for(int i = n - 1;i >= 0;--i)inv[i] = 1ll * inv[i + 1] * (i + 1) % P;

	for(int i = 0;i <= n;++i)A[i] = 1ll * fac[n - i] * F[n - i] % P,B[i] = inv[i];

	int l = init(n * 2);

	NTT(A,l,1);NTT(B,l,1);

	for(int i = 0;i < l;++i)A[i] = 1ll * A[i] * B[i] % P;

	NTT(A,l,-1);

	for(int i = 0;i < l;++i)B[i] = 0;

	for(int i = 0;i <= n;++i)G[i] = 1ll * inv[i] * A[n - i] % P;

	for(int i = 0;i < l;++i)A[i] = 0;

	for(int i = 0;i <= n;++i)G[i] = 1ll * power(inver(i + 1),m) * G[i] % P;

	for(int i = 0;i <= n;++i)A[i] = 1ll * fac[n - i] * G[n - i] % P,B[i] = 1ll * ((i & 1 ? P - 1 : 1)) * inv[i] % P;

	NTT(A,l,1);NTT(B,l,1);

	for(int i = 0;i < l;++i)A[i] = 1ll * A[i] * B[i] % P;

	NTT(A,l,-1);

	for(int i = 0;i <= n;++i)cout << 1ll * A[n - i] * inv[i] % P << " ";cout << endl;

	return 0;

}