description

给你一个长度为\(n\)的数列\(a_i\)，求它的\(k\)次前缀和模\(998244353\)。（就是做\(k\)次前缀和后的数列）

\(n\le10^5,k\le2^{60}\)。

sol

设\(F_t(x)\)表示数列在做过\(t\)次前缀和之后的生成函数。

尝试构造一个函数\(G(x)\)，满足\(F_t(x)G(x)\equiv F_{t+1}(x) \mod x^n\)。

发现\(G(x)=\sum_{i=0}^{n}x^i\)。

所以有\(F_k(x)=F_0(x)G^k(x)\)。直接多项式快速幂即可，理论复杂度\(O(n\log n)\)。（用多项式\(\ln\)多项式\(\exp\)那套理论就可以做到复杂度与\(k\)无关）

以上那种方法我没写，谁来写一写看看能不能跑得过去吧。

考虑一下上式的组合意义。因为\(G(x)\)的每一项都是\(1\)，那么\([x^i]G^k(x)\)相当于从\(k\)个盒子里取出若干个球使取出来的总数为\(i\)的方案数。在这里认为盒子不同而球相同。而这个方案数显然是可以组合算的，用隔板法即可。

也就是说，\(G^k(x)=\sum_{i=0}^{n}\binom{i+k-1}{k-1}x^i\)。

发现\(k\)非常大不好预处理组合数。考虑组合数的一个同层的递推式：\(\binom{n+1}{m}=\binom{n}{m}\times\frac{n+1}{n-m+1}\)。

所以直接递推即可，复杂度\(O(n\log n)\)。

code

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 4e5+5;

const int mod = 998244353;

int n,k,len,rev[N],l,og[N],a[N],b[N];

int fastpow(int a,int b){

	int res=1;

	while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}

	return res;

}

void ntt(int *P,int opt){

	for (int i=0;i<len;++i) if (i<rev[i]) swap(P[i],P[rev[i]]);

	for (int i=1;i<len;i<<=1){

		int W=fastpow(3,(mod-1)/(i<<1));

		if (opt==-1) W=fastpow(W,mod-2);

		og[0]=1;for (int j=1;j<i;++j) og[j]=1ll*og[j-1]*W%mod;

		for (int p=i<<1,j=0;j<len;j+=p)

			for (int k=0;k<i;++k){

				int x=P[j+k],y=1ll*og[k]*P[j+k+i]%mod;

				P[j+k]=(x+y)%mod,P[j+k+i]=(x-y+mod)%mod;

			}

	}

	if (opt==-1) for (int i=0,Inv=fastpow(len,mod-2);i<len;++i) P[i]=1ll*P[i]*Inv%mod;

}

int main(){

	n=gi();long long tmp;scanf("%lld",&tmp);k=tmp%mod;

	for (int i=1;i<=n;++i) a[i]=gi();

	b[0]=1;

	for (int i=1;i<=n;++i) b[i]=1ll*b[i-1]*(i+k-1)%mod*fastpow(i,mod-2)%mod;

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

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

	ntt(a,1);ntt(b,1);

	for (int i=0;i<len;++i) a[i]=1ll*a[i]*b[i]%mod;

	ntt(a,-1);

	for (int i=1;i<=n;++i) printf("%d\n",a[i]);return 0;

}

巴特西

[LOJ6261]一个人的高三楼

description

sol

code

最新文章

热门文章