【XSY3241】暴風士兵

他是暴風士兵，我是傘兵。

我們考慮令\(C(x)=\sum_{i=0}^{exp}(exp-i)x^i\)，\(P(x)\)為扣\(i\)滴血的機率\(P_i\)的生成函數。

那麼不難發現，對于一個時間\(t\)，答案即為：

\[ans_t=\sum_{i=0}^{exp}C_iP_i

\]

然後我們不難發現，每經過一個時間點\(t\)，\(P(x)\times=(P_ix+(1-P_i))\)。

但這樣似乎還是\(n^2\)的，做不了呀。

我們考慮随便設一個斷點\(k\)，然後讓\(A(x)=\prod_{i=1}^k(P_ix+(1-P_i))\),\(B(x)=\prod_{i=k+1}^t(P_ix+(1-P_i))\)，于是就有：

\[\begin{aligned}

ans_t &= \sum_{i=0}^{exp} C_i [x^i]A(x)B(x)\\

&= \sum_{i=0}^{exp} C_i \sum_{j=0}^i A_jB_{i-j}\\

&= \sum_{i=0}^{exp} B_i \sum_{j=0}^{exp-i} C_{j+i}A_j\\

&= \sum_{i=0}^{exp} C'i[x^i]B(x)

\end{aligned}

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x<y?x-y+mod:x-y;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int qpow(int n,int k){
    int ret=1;
    while(k){
        if(k&1)ret=mul(ret,n);
        n=mul(n,n);
        k>>=1;
    }
    return ret;
}
int G[2][270010][20];
void init(int lim){
    for(int mid=1,dep=0;mid<lim;mid<<=1,dep++){
        int len=mid<<1;
        int gn=qpow(3,(mod-1)/len);
        int ign=qpow(gn,mod-2);
        int g=1,ig=1;
        for(int j=0;j<mid;++j,g=mul(g,gn),ig=mul(ig,ign)){
            G[1][j][dep]=g,G[0][j][dep]=ig;
        }
    }
}
int rev[270010];
void NTT(int *A,int lim,int opt){
    for(int i=0;i<lim;++i){
        rev[i]=(rev[i>>1]>>1)|((i&1)*(lim>>1));
        if(i<rev[i])swap(A[i],A[rev[i]]);
    }
    for(int mid=1,dep=0;mid<lim;mid<<=1,dep++){
        int len=mid<<1;
        for(int i=0;i<lim;i+=len){
            for(int j=0;j<mid;++j){
                int x=A[i+j],y=mul(G[opt][j][dep],A[i+j+mid]);
                A[i+j]=add(x,y);
                A[i+j+mid]=dec(x,y);
            }
        }
    }
    if(!opt){
        int div=qpow(lim,mod-2);
        for(int i=0;i<lim;++i)A[i]=mul(A[i],div);
    }
}
int lst;
vector<int> c[400010];
vector<int> p[400010];
#define ls (o<<1)
#define rs (o<<1|1)
void solve(int o,int l,int r){
	if(l==r){
		int nowp;
		scanf("%d",&nowp);
		p[o].push_back(dec(1,add(nowp,lst)));p[o].push_back(add(nowp,lst));
//		cout<<p[o][0]<<" "<<p[o][1]<<" "<<c[o][0]<<" "<<c[o][1]<<endl;
		printf("%d\n",lst=(add(mul(c[o][0],p[o][0]),mul(c[o][1],p[o][1]))));
		return;
	}
	static int A[270010],B[270010];
	int mid=(l+r)/2;
	int len=(r-l+1),lenl=(mid-l+1),lenr=(r-mid);
	for(int i=0;i<=lenl;++i)c[ls].push_back(c[o][i]);
	solve(ls,l,mid);
	int lim=1;
	while(lim<=len+lenl)lim<<=1;
	for(int i=0;i<=len;++i)A[i]=c[o][i];
	for(int i=0;i<=lenl;++i)B[i]=p[ls][lenl-i];
	NTT(A,lim,1),NTT(B,lim,1);
	for(int i=0;i<lim;++i)A[i]=mul(A[i],B[i]);
	NTT(A,lim,0);
	for(int i=0;i<=lenr;++i)c[rs].push_back(A[i+lenl]);
	for(int i=0;i<lim;++i)A[i]=B[i]=0;
	solve(rs,mid+1,r);
	lim=1;
	while(lim<=lenl+lenr)lim<<=1;
	for(int i=0;i<=lenl;++i)A[i]=p[ls][i];
	for(int i=0;i<=lenr;++i)B[i]=p[rs][i];
	NTT(A,lim,1),NTT(B,lim,1);
	for(int i=0;i<lim;++i)A[i]=mul(A[i],B[i]);
	NTT(A,lim,0);
	for(int i=0;i<=len;++i)p[o].push_back(A[i]);
	for(int i=0;i<lim;++i)A[i]=B[i]=0;
	p[ls].clear(),p[rs].clear();
}
#undef ls
#undef rs
int main(){
	int exp,n;
	scanf("%d%d",&exp,&n);
	lst=exp;
	int lim=1;
	while(lim<=(n<<1))lim<<=1;
	init(lim);
	for(int i=0;i<=exp;++i)c[1].push_back(exp-i);
	for(int i=exp+1;i<=n;++i)c[1].push_back(0);
	solve(1,1,n);
}