[数学记录]P3711 仓鼠的数学题

· · 个人记录

题意:

设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),回答其系数。

------------ 本蒟蒻使用的伯努利数并不是正统的伯努利数,详情请见 [多项式计数杂谈](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需要多项式求逆。

#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;
}