自动搬运

查看原文

来自洛谷，原作者为

	command_block 众水皆昂首，饮月唯我一。

搬运于2025-08-24 22:10:19，当前版本为作者最后更新于2019-07-13 12:15:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

lyx_cjz的《<具体数学>选讲》哪里有啊?求教大佬!!!

看mrsrz大佬的题解没看懂,然后自己推了一下,来发一篇详细一点的题解:

一种思路是把这东西转换回普通多项式,卷在一起再换回来。

不过那样子复杂度是大常数的$O(nlog^2n)$,代码又长……

毕竟下降幂多项式的次数也是有限的,我们考虑利用点值来搞事情。

下降幂多项式的点值和EGF有着莫大的关系。

题目给了我们两个下降幂多项式$F(x),G(x)$我们设$F[n]$为$F(x)$的第$n$项系数。

我们写出点值的EGF: $F^\#=\sum\limits_{i=0}^∞\dfrac{F(i)}{i!}x^i$

那么,先来手玩$x^{\underline{n}}$的点值EGF:

$\sum\limits_{i=0}^∞\dfrac{i^{\underline{n}}}{i!}x^i==\sum\limits_{i=0}^∞\dfrac{1}{(i-n)!}x^i=x^n\sum\limits_{i=0}^∞\dfrac{1}{i!}x^i=e^xx^n$

那么$F(n)=\sum\limits_{i=0}^∞F[i]n^{\underline{i}}$

就相当于下降幂多项式的点值的EGF为$F^\#=\sum\limits_{i=0}^∞\dfrac{x^i}{i!}\sum\limits_{j=0}^∞F[j]i^{\underline{j}}$

交换和式得到:$=\sum\limits_{j=0}^∞F[j]\sum\limits_{i=0}^∞\dfrac{x^i}{i!}i^{\underline{j}}$

$=\sum\limits_{j=0}^∞F[j]\sum\limits_{i=0}^n\dfrac{i^{\underline{j}}}{i!}x^i$

根据上文的结论$\sum\limits_{i=0}^∞\dfrac{i^{\underline{n}}}{i!}x^i=e^xx^n$,式子变为

$=\sum\limits_{i=0}^∞F[i]e^xx^i=e^x\sum\limits_{i=0}^∞F[i]x^i$

也就是说,我们把$F[]$当成普通多项式,卷上$e^x$就能得到点值的EGF啦!

点值EGF点乘就好,然后在逆运算回去,具体方法是卷上$e^{-x}$,毫无毛病。

Tips:$e^{-x}$并不用求逆,其$=\sum\limits_{i=0}^∞\dfrac{(-1)^i}{i!}x^i$

#include<algorithm>
#include<cstdio>
#define mod 998244353
#define G 3
#define Maxn 200500
using namespace std;
int r[Maxn<<2];
long long invn,invG,fac[Maxn],inv[Maxn];
long long powM(long long a,long long t=mod-2)
{
  long long ans=1,buf=a;
  while(t){
  	if(t&1)ans=(ans*buf)%mod;
  	buf=(buf*buf)%mod;
  	t>>=1;
  }return ans;
}
void NTT(long long *f,bool op,int n)
{
  for (int i=0;i<n;i++)
    if (r[i]<i)swap(f[r[i]],f[i]);
  for (int len=1;len<n;len<<=1){
    int w=powM(op==1 ? G:invG,(mod-1)/len/2);
  	for (int p=0;p<n;p+=len+len){
  	  long long buf=1;
  	  for (int i=p;i<p+len;i++){
  	  	int sav=f[i+len]*buf%mod;
  	  	f[i+len]=f[i]-sav;
  	  	if (f[i+len]<0)f[i+len]+=mod;
  	  	f[i]=f[i]+sav;
  	  	if (f[i]>=mod)f[i]-=mod;
  	  	buf=buf*w%mod;
        }//F(x)=FL(x^2)+x*FR(x^2)
         //F(W^k)=FL(w^k)+W^k*FR(w^k)
         //F(W^{k+n/2})=FL(w^k)-W^k*FR(w^k)
    }
  }
}
void Init(int lim)
{
  inv[1]=inv[0]=fac[0]=1;
  for (int i=1;i<=lim;i++)fac[i]=fac[i-1]*i%mod;
  for (int i=2;i<=lim;i++)
  	inv[i]=inv[mod%i]*(mod-mod/i)%mod;
  for (int i=2;i<=lim;i++)inv[i]=inv[i-1]*inv[i]%mod;
}
long long s[Maxn<<2];
void FDT(long long *f,int n,bool op)
{
  if (op)
	for (int i=0;i<n;i++)s[i]=inv[i];
  else 
	for (int i=0;i<n;i++)
	  if (i&1)s[i]=mod-inv[i];
      else s[i]=inv[i];
  int len=1;for (;len<n+n;len<<=1);
  for (int i=n;i<len;i++)s[i]=0;
  for (int i=0;i<len;i++)
    r[i]=(r[i>>1]>>1)|(i&1?len>>1:0);
  NTT(f,1,len);NTT(s,1,len);
  for (int i=0;i<len;i++)f[i]=f[i]*s[i]%mod;
  NTT(f,0,len);invn=powM(len);
  for (int i=0;i<n;i++)f[i]=f[i]*invn%mod;
  for (int i=n;i<len;i++)f[i]=0;
}
int n,m;
long long f[Maxn<<2],g[Maxn<<2];
int main()
{
  scanf("%d%d",&n,&m);
  invG=powM(G);
  n++;m++;
  for (int i=0;i<n;i++)scanf("%lld",&f[i]);
  for (int i=0;i<m;i++)scanf("%lld",&g[i]);
  int cnt=n+m-1;
  Init(cnt);
  FDT(f,cnt,1);FDT(g,cnt,1);
  for (int i=0;i<cnt;i++)
	f[i]=f[i]*g[i]%mod*fac[i]%mod;
  FDT(f,cnt,0);
  for (int i=0;i<cnt;i++)printf("%lld ",f[i]);
  return 0;
}