传送门


题面

Description

小南有一套可爱的玩具小人,它们各有不同的职业。

有一天,这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈,它们有的面朝圈内,有的面朝圈外。如下图:

<img src="http://img.uoj.ac/problem/260/toy.png"/ style="width:500px;">

这时 singer 告诉小南一个谜题:“眼镜藏在我左数第 3 个玩具小人的右数第 1 个玩具小人的左数第 2 个玩具小人那里。”

小南发现,这个谜题中玩具小人的朝向非常关键,因为朝内和朝外的玩具小人的左右方向是相反的: 面朝圈内的玩具小人,它的左边是顺时针方向,右边是逆时针方向;而面向圈外的玩具小人,它的左边是逆时针方向,右边是顺时针方向。

小南一边艰难地辨认着玩具小人,一边数着:

“singer 朝内,左数第 3 个是 archer。

“archer 朝外,右数第 1 个是 thinker。

“thinker 朝外,左数第 2 个是 writer。

“所以眼镜藏在 writer 这里!”

虽然成功找回了眼镜,但小南并没有放心。如果下次有更多的玩具小人藏他的眼镜,或是谜题的长度更长,他可能就无法找到眼镜了。因此,为了解决问题,他决定让自己的玩具小人们互相战斗,杀死对方,以减少玩具小人的数量,这样就不会有那么多的麻烦了。

小南一共有$N$种不同的玩具小人,每种玩具小人的数量都可以被认为是无限大。每种玩具小人都有特定的血量,第$i$种玩具小人的血量就是整数$i$。此外,每种玩具小人还有自己的攻击力,攻击力可以是任意非负整数,且两种不同的玩具小人的攻击力可以相同。我们把第$i$种玩具小人的血量和攻击力表示成$a_i$和$b_i$。

为了让玩具小人们进行战斗,小南打算把一些小人选出来,编成队伍。一个队伍可以表示成一个由玩具小人组成的序列:$(p_1,p_2,...,p_l)$,其中$p_i$表示队伍中第$i$个玩具小人的种类,$l$为队伍的长度。对于不同的$i$,$p_i$可以相同。两个队伍被认为相同,当且仅当长度相同,且每个位置的玩具小人种类都分别相同。

一个队伍也有血量和攻击力两个属性,记为$a_t,b_t$。队伍的血量就是每个玩具小人的血量之和,而队伍攻击力可能会由于队伍内部产生矛盾而减小,对于长度为$l$的队伍,队伍的攻击力为每个玩具小人的攻击力之乘积除以$l$的阶乘。同时,当$l$大于等于某个常数$c$时,攻击力会有一个额外的加成:乘以$(1+\frac{l!}{(l-c)!})$。也就是说:

$$a_t=\sum_{i=1}^l a_{p_i},\\ b_t= \begin{cases} \frac1{l!}\prod_{i=1}^l b_{p_i} & ,l<c\\ (\frac1{l!}+\frac1{(l-c)!})\prod_{i=1}^l b_{p_i} & ,l\geq c \end{cases}$$

然而,小南的玩具小人们对小南的独裁统治感到愤怒,准备联合起来发起民主运动。为了旗帜鲜明地反对动乱,小南必须了解清楚玩具小人们的战斗力。不幸的是,由于玩具小人数量过多,小南已经忘记每种玩具小人的战斗力具体是多少了。现在,小南掌握的情报只有对于每个$1$和$N$之间的整数$i$,所有血量等于$i$的不同队伍的战斗力之和对$998244353$取模的值是多少(关于有理数如何对质数取模,请参考Hint部分)。他希望你根据已有的情报,还原出每种玩具小人的战斗力对$998244353$取模的结果 。如果镇压成功了,小南会请你到北京去做一回总书记(当然是北京玩具协会的总书记)。

Input

第一行包含两个整数$N,c$,$N$为玩具小人的种类数,$c$为题目描述中提到的某个常数。保证$1\leq N\leq60000,0\leq c\leq N$。

第二行包含$N$个数$s_1,s_2,...,s_N$,表示小南掌握的情报,即$s_i$表示所有血量等于$i$的不同队伍的战斗力之和对$998244353$取模的结果。保证$0\leq s_i < 998244353$。

Output

输出包含$N$行,每行一个整数$b_i$,表示第$i$种玩具小人的攻击力对$998244353$取模的结果。如果无解或有多组解,请输出$\int_0^{+\infty}x\frac{4x^2}{\alpha^3\sqrt{\pi}}e^\frac{-x^2}{\alpha^2}dx$关于$\alpha$的表达式。

Sample Input 1

3 1 2 499122178 665496236

Sample Output 1

1 0 0

Sample Explanation

$a_1=1,b_1=1$ $a_2=2,b_2=0$ $a_3=3,b_3=0$

$s_1=(\frac1{1!}+\frac1{0!})b_1=2$

$s_2=(\frac1{1!}+\frac1{0!})b_2+(\frac1{2!}+\frac1{1!})b_1b_1=\frac12$ $\frac12\equiv499122178\pmod {998244353}$

$s_3=(\frac1{1!}+\frac1{0!})b_3+(\frac1{2!}+\frac1{1!})b_1b_2+(\frac1{2!}+\frac1{1!})b_2b_1+(\frac1{3!}+\frac1{2!})b_1b_1b_1=\frac23$ $\frac23\equiv665496236\pmod {998244353}$

Sample Input 2

5 2 233 2333 23333 233333 2333333

Sample Output 2

233 499043076 706053258 488828520 182366701

Hint

设$x=a/b$为某个有理数,则$x$对某个质数$P$取模的值,就是$0$~$P-1$之间的某个整数$y$,使得$by\equiv a\pmod P$。可以证明当$P$不整除$b$时,这样的$y$有且仅有一个。

对于$30\%$的数据,满足$1\leq N \leq 500$。

对于另$30\%$的数据,满足$c=0$。

对于$100\%$的数据,满足$1\leq N \leq 60000,0\leq c\leq N,0\leq s_i<998244353$。


题解

首先考虑30分暴力做法,我们记$f_{i,j}$为血量为$i$,且长度为$j$的所有队伍的“所有玩具小人的战斗力乘积”之和(注意不是所有队伍的战斗力之和),我们根据这个东西,可以直接算出这些队伍的战斗力之和。设当前已经确定了所有$j<i$的$b_j$,我们也可以直接dp得到所有满足$j\geq2$的$f_{i,j}$。经过计算,我们就能得到$f_{i,1}$,进而得到$b_i$。

为了拿到剩下的分数,我们需要用到一点微小的生成函数。记$F$为$N$种玩具小人的战斗力的生成函数,即$F=\sum_{1\leq k\leq N} b_kx^k$。我们的目的就是最终求出这个生成函数。

记$s_0,s_1,s_2,...,s_N$的生成函数为$A$,即$A=\sum_{0\leq k\leq N} s_kx^k$,这里我们令$s_0$在$c=0$时为$2$,否则为$1$。经过观察,我们可以发现,我们其实就是要满足$(F^c+1)e^F=A$。

对于剩下的30分,式子变成了$2e^F=A$,也就是$F=\ln\frac A2$。直接实现一个多项式求对数就能拿到这30分了。

对于剩下的40分,我们需要满足$g(F)=(F^c+1)e^F-A=0$,考虑用牛顿迭代解这个方程。设我们已经求得了$F_0$,使得$g(F_0)\equiv0\pmod {x^{N/2}}$,我们需要用$F_0$求出$F$,满足$g(F)\equiv0\pmod {x^N}$。注意这里的$N$都是2的幂,如果一开始$N$不是2的幂,我们可以直接把$N$赋成大于等于$N$的最小的2的幂。

考虑在$F_0$处对$g$泰勒展开,即$$g(F)=g(F_0)+g'(F_0)(F-F_0)+g''(F_0)(F-F_0)^2...$$由于$F$与$F_0$的前$N/2$项相同,$F-F_0$的最小非零项的次数一定大于等于$N/2$,所以$g''(F_0)(F-F_0)^2$之后的项都会在模$x^N$的意义下直接被模掉。这时式子就变成了:$$g(F)\equiv g(F_0)+g'(F_0)(F-F_0)\pmod {x^N}$$代入$g(F)\equiv0\pmod{x^N}$,经过变形可以化为:$$F\equiv F_0-\frac{g(F_0)}{g'(F_0)}\pmod {x^N}$$

我们把$g(F)=F^ce^F+e^F-A,g'(F)=cF^{c-1}e^F+F^ce^F+e^F$代入式子,就变成了:$$F\equiv F_0-\frac{F_0^ce^{F_0}+e^{F_0}-A}{cF_0^{c-1}e^{F_0}+F_0^ce^{F_0}+e^{F_0}}\pmod {x^N}$$

这里直接用多项式求exp和多项式求逆做一下就行了。由于涉及到的所有多项式操作都能在$O(N\log N)$内完成,我们解方程的复杂度就是$T(N)=T(N/2)+O(N\log N)=O(N\log N)$。由于常数过大,就只能跑10W以下了QAQ。。。


代码

#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#define LL long long
#define MAXN 530000
#define MAXW 524288
using namespace std;

const LL P=998244353;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res;
}

int n,c,sizew;
LL w[MAXN],inv_v[MAXN];

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

void init(){
    w[0]=1;
    w[1]=getPow(3,(P-1)/MAXW);
    for(int i=2;i<MAXW;i++) w[i]=w[i-1]*w[1]%P;
    inv_v[1]=1;
    for(int i=2;i<MAXN;i++) inv_v[i]=P-(P/i)*inv_v[P%i]%P;
}

void FFT(LL *a,int len,int flag){
    static int rev[MAXN],revlen;
    if(revlen!=len){
        revlen=len;
        for(int i=1;i<len;i++) rev[i]=rev[i>>1]>>1|((i&1)?(len>>1):0);
    }
    for(int i=0;i<len;i++)
        if(i<rev[i]) a[i]^=a[rev[i]]^=a[i]^=a[rev[i]];
    for(int l=2;l<=len;l<<=1){
        int l2=l>>1;
        for(int i=0;i<len;i+=l){
            for(int j=0;j<l2;j++){
                LL t1=a[i+j],t2=a[i+j+l2]*w[MAXW/l*j];
                a[i+j]=(t1+t2)%P;
                a[i+j+l2]=(t1-t2)%P;
            }
        }
    }
    if(flag==-1){
        for(int i=1;i<len;i++) if(i<len-i) a[i]^=a[len-i]^=a[i]^=a[len-i];
        LL invn=getPow(len,P-2);
        for(int i=0;i<len;i++) a[i]=a[i]*invn%P;
    }
}

void getInv(LL *b,LL *a,int len){
    if(len==1){
        b[0]=getPow(a[0],P-2);
        return;
    }
    static LL t1[MAXN],t2[MAXN];
    getInv(t1,a,len>>1);
    for(int i=len>>1;i<len<<1;i++) t1[i]=0;
    for(int i=0;i<len;i++) t2[i]=a[i],t2[i+len]=0;
    FFT(t1,len<<1,1); FFT(t2,len<<1,1);
    for(int i=0;i<len<<1;i++) t1[i]=(2*t1[i]-t2[i]*t1[i]%P*t1[i])%P;
    FFT(t1,len<<1,-1);
    for(int i=0;i<len;i++) b[i]=t1[i];
}

void getLn(LL *b,LL *a,int len){
    static LL t1[MAXN],t2[MAXN];
    getInv(t1,a,len);
    for(int i=1;i<len;i++) t2[i-1]=a[i]*i%P;
    for(int i=0;i<len;i++) t1[i+len]=t2[i+len]=0;
    FFT(t1,len<<1,1); FFT(t2,len<<1,1);
    for(int i=0;i<len<<1;i++) t1[i]=t1[i]*t2[i]%P;
    FFT(t1,len<<1,-1);
    b[0]=0;
    for(int i=1;i<len;i++) b[i]=t1[i-1]*inv_v[i]%P;
}

void getExp(LL *b,LL *a,int len){
    if(len==1){ b[0]=1; return; }
    static LL t1[MAXN],t2[MAXN],t3[MAXN],t4[MAXN];
    getExp(t1,a,len>>1);
    for(int i=len>>1;i<len<<1;i++) t1[i]=0;
    getLn(t2,t1,len);
    for(int i=0;i<len>>1;i++){
        t3[i]=t1[i];
        t4[i]=t1[i];
        t4[i+(len>>1)]=0;
        t2[i]=t2[i+(len>>1)]-a[i+(len>>1)];
        t2[i+(len>>1)]=0;
    }
    FFT(t4,len,1); FFT(t2,len,1);
    for(int i=0;i<len;i++) t4[i]=t4[i]*t2[i]%P;
    FFT(t4,len,-1);
    for(int i=0;i<len>>1;i++){
        b[i]=t3[i];
        b[i+(len>>1)]=-t4[i];
    }
}

void getPow(LL *b,LL *a,int k,int len){
    static LL t1[MAXN],t2[MAXN];
    int d=0;
    while(a[d]==0 && d<len) d++;
    if(d==len){
        for(int i=0;i<len;i++) b[i]=0;
        if(k==0) b[0]=1;
        return;
    }
    LL c=a[d],invc=getPow(c,P-2);
    for(int i=0;i<len;i++)
        if(i+d<len) t2[i]=a[i+d]*invc%P;
        else t2[i]=0;
    getLn(t1,t2,len);
    for(int i=0;i<len;i++) t1[i]=t1[i]*k%P;
    getExp(t2,t1,len);
    for(int i=0;i<len && i<d*k;i++) b[i]=0;
    c=getPow(c,k);
    for(int i=d*k;i<len;i++)
        b[i]=t2[i-d*k]*c%P;
}

void getMul(LL *b,LL *a,int len){
    static LL t1[MAXN],t2[MAXN];
    for(int i=0;i<len;i++) t1[i]=b[i],t2[i]=a[i],t1[i+len]=t2[i+len]=0;
    FFT(t1,len<<1,1); FFT(t2,len<<1,1);
    for(int i=0;i<len<<1;i++) t1[i]=t1[i]*t2[i]%P;
    FFT(t1,len<<1,-1);
    for(int i=0;i<len;i++) b[i]=t1[i];
}

void solve(LL *b,LL *a,int len){
    if(len==1){ b[0]=0; return; }
    static LL t1[MAXN],t2[MAXN],t3[MAXN],t4[MAXN],t5[MAXN],t6[MAXN],t7[MAXN];
    solve(t1,a,len>>1);
    for(int i=0;i<len>>1;i++) t3[i]=t1[i],t3[i+(len>>1)]=0;
    getPow(t2,t3,c-1,len);
    getExp(t5,t3,len);
    for(int i=0;i<len;i++) t4[i]=t6[i]=t5[i];
    getMul(t5,t2,len);
    for(int i=0;i<len;i++) t6[i]=(t6[i]+t5[i]*c)%P;
    getMul(t5,t3,len);
    for(int i=0;i<len;i++){
        t4[i]=(t4[i]+t5[i]-a[i])%P;
        t6[i]=(t6[i]+t5[i])%P;
    }
    getInv(t7,t6,len);
    getMul(t4,t7,len);
    for(int i=0;i<len;i++) b[i]=(t3[i]-t4[i])%P;
}

void solve2(LL *b,LL *a,int len){
    for(int i=1;i<len;i++) a[i]=a[i]*inv_v[2]%P;
    getLn(b,a,len);
}

LL a[MAXN],b[MAXN];

int main(){
#ifdef DEBUG
    //freopen("toy.in","r",stdin);
#endif
    scanf("%d%d",&n,&c);
    for(sizew=1;sizew<=n;sizew<<=1);
    init();
    a[0]=1;
    for(int i=1;i<=n;i++) a[i]=read();
    if(c==0) solve2(b,a,sizew);
    else solve(b,a,sizew);
    for(int i=1;i<=n;i++)
        printf("%lld\n",(b[i]+P)%P);
    return 0;
}