[数学记录]P3711 仓鼠的数学题
command_block
2019-11-04 21:46:37
**题意:**
设$S_k(x)=\sum\limits_{i=0}^xi^k$,即有关自然数$k$次幂和的多项式。
(这里$0^0=1$)
给出$A[0...n]$,求$F(x)=\sum\limits_{k=0}^nA[k]S_k(x)$,回答其系数。
$n\leq 2.5\times10^5$ ,对$998244353$取模。
------------
本蒟蒻使用的伯努利数并不是正统的伯努利数,详情请见 [多项式计数杂谈](https://www.luogu.com.cn/blog/command-block/sheng-cheng-han-shuo-za-tan)
令$B(x)=\dfrac{x}{e^x-1}$,可得
根据伯努利数的结论$S_k(x)=k!\sum\limits_{i=0}^{k}\dfrac{B[k-i]x^{i+1}}{(i+1)!}+x^k$
$F(x)=\sum\limits_{k=0}^nA[k]\left(k!\sum\limits_{i=0}^{k}\dfrac{B[k-i]x^{i+1}}{(i+1)!}+x^k\right)$
$=\sum\limits_{k=0}^nA[k]k!\sum\limits_{i=0}^{k}\dfrac{B[k-i]x^{i+1}}{(i+1)!}+\sum\limits_{k=0}^nA[k]x^k$
右边一小部分最后单独累加就好了,暂时略去。
交换和式可得 :
$=\sum\limits_{i=0}^{n}x^{i+1}\sum\limits_{k=i}^n\dfrac{B[k-i]}{(i+1)!}A[k]k!$
脑补一下 :
$F[i+1]=\dfrac{1}{(i+1)!}\sum\limits_{k=i}^nB[k-i]A[k]k!$
差卷积+位移即可。
求$B$需要多项式求逆。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define mod 998244353
#define G 3
#define Maxn 270005
using namespace std;
inline int read()
{
register int X=0;
register char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
ll powM(ll a,ll t=mod-2)
{
ll ans=1,buf=a;
while(t){
if(t&1)ans=(ans*buf)%mod;
buf=(buf*buf)%mod;
t>>=1;
}return ans;
}
int tr[Maxn<<1];
ll invG;
void NTT(ll *f,short op,int n)
{
for (int i=0;i<n;i++)
if (i<tr[i])swap(f[i],f[tr[i]]);
for(int p=2;p<=n;p<<=1){
int len=p/2;
ll tG=powM(op==1 ? G:invG,(mod-1)/p);
for(int k=0;k<n;k+=p){
ll buf=1;
for(int l=k;l<k+len;l++){
int tt=buf*f[len+l]%mod;
f[len+l]=f[l]-tt;
if (f[len+l]<0)f[len+l]+=mod;
f[l]+=tt;
if (f[l]>=mod)f[l]-=mod;
buf=buf*tG%mod;
}
}
}
}
ll _g1[Maxn<<1];
void times(ll *f,ll *g,int len,int lim)
{
int m=len+len,n;
for(int i=0;i<len;i++)_g1[i]=g[i];
#define g _g1
for(n=1;n<m;n<<=1);
for(int i=len;i<n;i++)g[i]=0;
ll invn=powM(n);
for(int i=0;i<n;i++)
tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(f,1,n);NTT(g,1,n);
for(int i=0;i<n;++i)f[i]=f[i]*g[i]%mod;
NTT(f,-1,n);
for(int i=0;i<lim;++i)
f[i]=f[i]*invn%mod;
for(int i=lim;i<n;++i)f[i]=0;
#undef g
}
ll _w2[Maxn<<1],_r2[Maxn<<1];
void inv(ll *f,int m)
{
int n;for (n=1;n<m;n<<=1);
#define w _w2
#define r _r2
w[0]=powM(f[0]);
for (int len=2;len<=n;len<<=1){
for (int i=0;i<(len>>1);i++)
r[i]=(w[i]<<1)%mod;
times(w,w,len>>1,len);
times(w,f,len,len);
for (int i=0;i<len;i++)
w[i]=(r[i]-w[i]+mod)%mod;
}for (int i=0;i<m;i++)f[i]=w[i];
for (int i=0;i<n;i++)w[i]=r[i]=0;
#undef w
#undef r
}
ll fac[Maxn],ifac[Maxn];
void Init(int lim)
{
fac[0]=ifac[0]=ifac[1]=1;
for (int i=2;i<=lim;i++)
ifac[i]=ifac[mod%i]*(mod-mod/i)%mod;
for (int i=1;i<=lim;i++){
fac[i]=fac[i-1]*i%mod;
ifac[i]=ifac[i-1]*ifac[i]%mod;
}
}
int n;
ll A[Maxn<<1],B[Maxn<<1],F[Maxn];
int main()
{
invG=powM(G);
scanf("%d",&n);n++;
Init(n+5);
for (int i=0;i<n;i++){
B[i]=ifac[i+1];
F[i]=read();
A[n-i-1]=F[i]*fac[i]%mod;
}inv(B,n);
times(A,B,n,n);
for (int i=1;i<=n;i++)
F[i]=(F[i]+A[n-i]*ifac[i])%mod;
for (int i=0;i<=n;i++)
printf("%lld ",F[i]);
return 0;
}
```