【LGP5349】幂

题目

比较厉害的题目了

求

\[\sum_{i=0}^{\infty}\sum_{j=0}^nf_ji^jr^i
\]

改变一下求和顺序

\[\sum_{j=0}f_j\sum_{i=0}^{\infty}i^jr^i
\]

我们发现只要对于\(k=[0,m]\)，求出\(\sum_{i=0}^{\infty}i^kr^i\)就可以了

不妨把这个要求的东西看成一个关于\(r\)的多项式\(g_k(r)=\sum_{i=0}^{\infty}i^kr^i\)

显然有

\[\frac{g_k(r)}{r}=\sum_{i=0}^{\infty}i^kr^{i-1}
\]

对于\(k>0\)，就有\(\frac{g_k(r)}{r}=\sum_{i=0}^{\infty}(i+1)^kr^{i}\)

我们那这个式子减掉\(g_k(r)\)

即

\[(\frac{1}{r}-1)g_k(r)=\sum_{i=0}^\infty ((i+1)^k-i^k)r^i
\]

我们用二项式订定理展开一下\((i+1)^k-i^k\)，这个显然应该是\(\sum_{j=0}^{k-1}\binom{k}{j}i^j\)

即

\[(\frac{1}{r}-1)g_k(r)=\sum_{i=0}^\infty r^i\sum_{j=0}^{k-1}\binom{k}{j}i^j
\]

改变一下求和顺序

\[(\frac{1}{r}-1)g_k(r)=\sum_{j=0}^{k-1}\binom{k}{j}\sum_{i=0}^\infty i^jr^i=\sum_{j=0}^{k-1}\binom{k}{j}g_j(r)
\]

我们大力拆开组合数就得到了

\[\frac{g_k(r)}{k!}=\sum_{i=0}^{k-1}\frac{g_j(r)}{j!}\times \frac{r}{(k-j)!\times (1-r)}
\]

显然自己卷自己，多项式求逆即可，注意边界\(g_0(r)=\sum_{i=0}^\infty r^i=\frac{1}{1-r}\)

代码

#include<bits/stdc++.h>

#define re register

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

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

}

const int maxn=262144+5;

const int mod=998244353;

const int G[2]={3,(mod+1)/3};

inline int ksm(int a,int b) {

	int S=1;

	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;

	return S;

}

int n,m,len,rev[maxn],fac[maxn],inv[maxn],ifac[maxn];

int a[maxn],b[maxn],C[maxn];

inline void NTT(int *f,int o) {

	for(re int i=0;i<len;i++) if(i<rev[i]) std::swap(f[i],f[rev[i]]);

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

		int ln=i>>1,og1=ksm(G[o],(mod-1)/i);

		for(re int t,og=1,l=0;l<len;l+=i,og=1)

			for(re int x=l;x<l+ln;++x) {

				t=1ll*f[x+ln]*og%mod;og=1ll*og*og1%mod;

				f[x+ln]=(f[x]-t+mod)%mod;f[x]=(f[x]+t)%mod;

			}

	}

	if(!o) return;

	int Inv=ksm(len,mod-2);

	for(re int i=0;i<len;i++) f[i]=1ll*f[i]*Inv%mod;

}

void Inv(int n,int *A,int *B) {

	if(n==1) {A[0]=ksm(B[0],mod-2);return;}

	Inv((n+1)>>1,A,B);len=1;

	while(len<n+n-1) len<<=1;

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

	for(re int i=0;i<n;i++) C[i]=B[i];

	for(re int i=n;i<len;i++) C[i]=0;

	NTT(C,0),NTT(A,0);

	for(re int i=0;i<len;i++) A[i]=(2ll*A[i]-1ll*C[i]*A[i]%mod*A[i]%mod+mod)%mod;

	NTT(A,1);for(re int i=n;i<len;i++) A[i]=0;

}

int main() {

	n=read(),m=read();fac[0]=ifac[0]=inv[1]=1;

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

	for(re int i=2;i<=n;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

	for(re int i=1;i<=n;i++) ifac[i]=1ll*ifac[i-1]*inv[i]%mod;

	int t=ksm(m,mod-2);t=(1+mod-t)%mod;t=ksm(t,mod-2);

	for(re int i=1;i<=n;i++) b[i]=1ll*ifac[i]*t%mod;

	b[0]=1;Inv(n+1,a,b);

	int ans=0;

	for(re int i=0;i<=n;i++) ans=(ans+1ll*fac[i]*a[i]%mod*read()%mod)%mod;

	printf("%d\n",1ll*ans*ksm(1-m+mod,mod-2)%mod);

	return 0;

}

巴特西

【LGP5349】幂

最新文章

热门文章